Tarjan 算法通过一次 DFS 求出有向图中所有强连通分量（SCC），时间复杂度 O(V+E)。它是图论中最重要的线性算法之一。
一、基本概念
- 强连通：有向图中 u 和 v 互相可达
- 强连通分量（SCC）：极大的强连通子图
- 缩点：将每个 SCC 视为一个超级节点，得到 DAG
二、核心概念：dfn 与 low
dfn[u]：DFS 访问 u 的时间戳（发现序）low[u]：u 通过子树中的边能回溯到的最早祖先的 dfn
判定规则：当 low[u] == dfn[u] 时，u 是一个 SCC 的根。
三、代码实现
public class TarjanSCC {
private List<List<Integer>> graph;
private int[] dfn, low;
private boolean[] onStack;
private Deque<Integer> stack;
private int timer;
private List<List<Integer>> sccs;
public List<List<Integer>> findSCCs(List<List<Integer>> graph) {
this.graph = graph;
int n = graph.size();
dfn = new int[n];
low = new int[n];
onStack = new boolean[n];
stack = new ArrayDeque<>();
sccs = new ArrayList<>();
timer = 0;
for (int i = 0; i < n; i++) {
if (dfn[i] == 0) {
dfs(i);
}
}
return sccs;
}
private void dfs(int u) {
dfn[u] = low[u] = ++timer;
stack.push(u);
onStack[u] = true;
for (int v : graph.get(u)) {
if (dfn[v] == 0) {
// 未访问：递归
dfs(v);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) {
// 已访问且在栈中：回边
low[u] = Math.min(low[u], dfn[v]);
}
}
// u 是 SCC 的根
if (low[u] == dfn[u]) {
List<Integer> scc = new ArrayList<>();
int w;
do {
w = stack.pop();
onStack[w] = false;
scc.add(w);
} while (w != u);
sccs.add(scc);
}
}
}