强连通分量（Tarjan）

图算法 · 有向图连通性 · O(V+E)

能互相到达的极大集合

在有向图里，如果一组节点两两都能互相到达（你能到我、我也能到你），且再加任何一个节点都做不到，这组节点就构成一个强连通分量（SCC）。把每个 SCC 缩成一个点，有向图就变成一张无环图（DAG）——这是很多高级图算法的第一步。朴素做法对每个点各跑一次 DFS 判断可达性太慢；Tarjan 用一趟 DFS 就求出所有 SCC。

dfn、low 和一个栈

DFS 给每个节点记两个数：dfn[u]——它被发现的次序（时间戳）；low[u]——从 u 的子树出发、至多经过一条回边能回溯到的最小 dfn。DFS 时把访问到的节点压入一个栈。low 在两处更新：子节点递归返回时 low[u]=min(low[u], low[子])；遇到一条指向还在栈里的节点 v 的回边时 low[u]=min(low[u], dfn[v])。

关键判据：当 low[u] == dfn[u] 时，说明 u 回不到任何更早的祖先，它就是一个 SCC 的根——此时把栈里 u 之上（含 u）的节点全部弹出，它们正好构成一个强连通分量。因为每个节点、每条边只处理一次，总复杂度 O(V+E)。

下面是一张 6 节点有向图。点「下一步」逐步看：节点右上角是 dfn/low、虚线环是当前在栈里的节点、琥珀环是当前节点、绿边是 DFS 树边、黄边是当前回边；每弹出一个 SCC，它的节点就着上同一种颜色。走到底，三个 SCC {0,1,2}、{3,4}、{5} 三色分明。右侧代码随每一步同步高亮。

访问节点 0：dfn=low=0，入栈

1function tarjan(n: number, adj: number[][]): number[][] {
const dfn = Array(n).fill(-1), low = Array(n).fill(-1);
const onStk = Array(n).fill(false), stk: number[] = [];
const sccs: number[][] = []; let idx = 0;
const dfs = (u: number) => {
  dfn[u] = low[u] = idx++;              // 发现 u：dfn=low=时间戳
  stk.push(u); onStk[u] = true;         // 入栈
  for (const v of adj[u]) {
    if (dfn[v] === -1) {                // 树边：v 未访问
      dfs(v);
      low[u] = Math.min(low[u], low[v]); // 子树回传
    } else if (onStk[v]) {              // 回边：v 在栈中
      low[u] = Math.min(low[u], dfn[v]);
    }
  }
  if (low[u] === dfn[u]) {              // u 是 SCC 根
    const comp: number[] = []; let w;
    do { w = stk.pop()!; onStk[w] = false; comp.push(w); }
    while (w !== u);                    // 弹栈到 u → 一个 SCC
    sccs.push(comp);
  }
};
for (let i = 0; i < n; i++) if (dfn[i] === -1) dfs(i);
return sccs;
25}

节点/边6 点 / 7 有向边

当前节点0（dfn=0, low=0）

栈[0]

已找 SCC0

1 / 17

强连通分量在哪里用

缩点：把每个 SCC 缩成一点得到 DAG，再在 DAG 上跑拓扑排序 / DP。
2-SAT：布尔约束可满足性判定，靠 SCC 判断 x 与 ¬x 是否同组。
依赖 / 死锁检测：有向环 = 循环依赖，SCC 一次找出所有环。

和拓扑排序正好互补：拓扑排序处理的是无环有向图（DAG），而 Tarjan 专门把有环的部分（每个 SCC）识别出来——两者合起来，任何有向图都能先缩点、再拓扑。

算法可视化

强连通分量（Tarjan）

能互相到达的极大集合

dfn、low 和一个栈

强连通分量在哪里用