Tarjan算法详解
Tarjan算法基础
Tarjan算法是一种经典的图论算法，主要用于解决有向图的强连通分量（SCC）以及无向图的双连通分量问题。本文将详细讲解其原理及实现。
有向图的强连通分量
在一个有向图中，如果任意两点之间都能互相到达，则称这部分为一个强连通分量。
基本概念
- 强连通：有向图 G 中任意两个节点互达。
- 强连通分量：极大强连通子图。
- 连通分量：所有节点间可互相到达的集合。
时间复杂度为 O(n + m)，其中 n 为点数，m 为边数。
算法逻辑
Tarjan 算法通过深度优先搜索（DFS）来遍历图，并利用两个数组记录每个节点的状态：
dfn[u]: 节点 u 的访问顺序。low[u]: 节点 u 能回溯到的最小访问顺序。
同时使用栈来存储当前可能属于同一个强连通分量的节点。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dfn[N], low[N], scc_id[N], scc_size[N];
bool in_stack[N];
vector<int> adj[N];
stack<int> stk;
int timestamp, scc_count;
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stk.push(u);
in_stack[u] = true;
for (auto &v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
++scc_count;
while (true) {
int v = stk.top(); stk.pop();
in_stack[v] = false;
scc_id[v] = scc_count;
scc_size[scc_count]++;
if (v == u) break;
}
}
}
无向图的双连通分量
无向图的双连通分量分为两种：
- E-DCC：边双连通分量。
- V-DCC：点双连通分量。
若移除某个节点或边后，图被分割成多个连通块，则该节点或边称为割点或桥。
边双连通分量
边双连通分量是指不包含桥的最大连通子图。
核心思想
通过 Tarjan 算法，可以找到所有的桥和边双连通分量。判断桥的条件是：
low[v] > dfn[u]，表示从 v 无法通过其他路径回到 u。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dfn[N], low[N], timestamp;
bool is_bridge[N];
vector<pair<int, int>> edges;
vector<int> adj[N];
stack<pair<int, int>> stk;
void tarjan(int u, int parent_edge) {
dfn[u] = low[u] = ++timestamp;
for (auto &edge_idx : adj[u]) {
auto &[v, edge_id] = edges[edge_idx];
if (!dfn[v]) {
stk.push({u, edge_id});
tarjan(v, edge_id);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
is_bridge[edge_id] = true;
}
} else if (edge_id != parent_edge) {
low[u] = min(low[u], dfn[v]);
if (dfn[v] < dfn[u]) stk.push({u, edge_id});
}
}
}
点双连通分量
点双连通分量是指不包含割点的最大连通子图。
核心思想
通过 Tarjan 算法，可以找到所有的割点和点双连通分量。判断割点的条件是：
- 根节点：至少有两个子树。
- 非根节点：
low[v] >= dfn[u]。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dfn[N], low[N], timestamp;
bool is_cutpoint[N];
vector<int> adj[N];
stack<int> stk;
int dcc_count;
void tarjan(int u, bool is_root) {
dfn[u] = low[u] = ++timestamp;
stk.push(u);
int child_count = 0;
for (auto &v : adj[u]) {
if (!dfn[v]) {
tarjan(v, false);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (!is_root || ++child_count > 1) is_cutpoint[u] = true;
vector<int> dcc;
while (true) {
int w = stk.top(); stk.pop();
dcc.push_back(w);
if (w == v) break;
}
dcc.push_back(u);
dcc_count++;
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
