Tarjan强连通分量查找器

伪代码

一次 DFS、一个栈、每个结点两个数字。核心洞见是：每个强连通分量都有唯一的根，也就是该分量中最先被发现的那个结点。

strongconnect(u):
    disc[u] = low[u] = ++时间
    栈.压入(u); 在栈上[u] = 真

    对每条边 (u, v):
        若 v 未访问:
            strongconnect(v)
            low[u] = min(low[u], low[v])
        否则若 在栈上[v]:
            low[u] = min(low[u], disc[v])
        // 否则：v 属于已完成的强连通分量，忽略

    若 low[u] == disc[u]:        // u 是分量的根
        把栈弹到 u（含 u）为止
        弹出的这一组就是一个强连通分量

「在栈上」这项检查正是 Tarjan 与朴素 low-link 方案的分水岭。指向一个已访问、但已归入某个完成分量的结点的边，对你当前所在的分量没有任何信息，必须跳过；把它算进来会把两个本就彼此独立的强连通分量错误地合并。还要注意其中的不对称：树边并入的是 low[v]，回边并入的是 disc[v]，把两者搞混是另一个经典错误。

分步示例演算

在一个同时包含三元环、二元环以及一个不属于任何环的结点的有向图上运行 Tarjan。

示例图: 有向边 A 到 B、B 到 C、C 到 A、B 到 D、D 到 E、E 到 D，以及 C 到 F。

1. 沿 A、B、C 下探. disc 与 low 初始相同：A 得 1，B 得 2，C 得 3。三者都在栈上。
2. C 到 A 是回边. A 已访问且仍在栈上，因此 low[C] = min(3, disc[A] = 1) = 1。注意这里用的是 disc[A] 而不是 low[A]。
3. C 到 F，F 单独出栈. F 的 disc 为 4，且没有出边，因此 low[F] 保持为 4。由于 low[F] 等于 disc[F]，F 是分量的根，独自作为分量 {F} 出栈。不在任何环上的结点总是自成一个单元素强连通分量。
4. B 到 D 到 E，E 又绕回来. D 的 disc 为 5，E 的 disc 为 6。边 E 到 D 发现 D 在栈上，因此 low[E] = min(6, disc[D] = 5) = 5。E 不是根，因为 low[E] 的 5 不等于 disc[E] 的 6，此时还不会弹出任何东西。
5. D 是根. 回到 D，low[D] = min(5, low[E] = 5) = 5，与 disc[D] 相等。D 是分量的根，栈依次弹出 E 和 D，得到分量 {D, E}。
6. A 是根. 继续回溯，low[B] = min(2, low[C] = 1, low[D] = 5) = 1，low[A] = min(1, low[B] = 1) = 1，与 disc[A] 相等。栈依次弹出 C、B、A，得到 {A, B, C}。

最终的 low-link 值为 A 1、B 1、C 1、F 4、D 5、E 5，分量按 {F}、{D, E}、{A, B, C} 的顺序产出。有两点值得注意。分量是按缩点图的逆拓扑序输出的，这也是 Tarjan 通常作为求解 2-SAT 第一步的原因。另外，F 虽然能从环上抵达却无法返回，它被正确地划成独立分量，而没有被并入 {A, B, C}。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

一次深度优先搜索访问每个结点一次，并对每条有向边恰好检查一次，因此为 O(V + E)。每个结点只被压栈一次、弹栈一次，整个运行过程中的栈操作合计为 O(V)。额外状态是每个结点的发现时间、low-link 值和在栈标记，再加上递归栈，全都是 O(V)。Tarjan 一趟就能完成，而 Kosaraju 需要两次完整遍历外加构造转置图，这也是尽管两者都是线性的、实践中却通常首选 Tarjan 的原因。

何时使用塔扬强连通分量算法，何时不宜

三种线性的强连通分量算法渐进代价相同，因此选择取决于常数因子、内存以及代码写对的难易程度。

常见陷阱

• 在回边上用 low[v] 而不是 disc[v]. 对树边你并入 low[v]；对指向栈上结点的回边你并入 disc[v]。在回边上使用 low[v] 可能把另一个分量的值牵扯进来，从而合并本应分开的强连通分量。这两种情形确实不同。
• 省略「在栈上」的检查. 指向一个已访问、且已被弹出并归入完成分量的结点的边，必须完全忽略。缺少这项检查，low-link 值就会跨越分量边界渗漏，在任何含有横叉边的图上输出都是错的。
• 弹栈时忘记清除在栈标记. 每个被弹出并归入分量的结点都必须清掉它的标记。若继续留着，之后的回边判断会针对已经不在栈上的结点触发，从而悄无声息地破坏后续分量。
• 在超大图上使用递归. Tarjan 天生是递归的，递归深度等于最长路径的长度。在数十万结点串成一条链的图上，调用栈会溢出，必须改写为显式栈版本。这比改写普通 DFS 更棘手，因为 low-link 的更新必须在每个孩子返回之后进行。
• 假定存在并不存在的分量顺序. Tarjan 按缩点图的逆拓扑序输出分量，而不是按与结点标号有关的任何顺序。若你需要正向拓扑序，请把输出反转。

常见问题

什么是强连通分量？

有向图的强连通分量是一个极大的结点集合，其中任意一个结点都能沿有向边抵达其余所有结点。「极大」很关键：你无法再加入任何结点还保持这一性质。不位于任何有向环上的结点自成一个分量。

Tarjan 算法是怎样工作的？

它执行一次深度优先搜索，为每个结点赋予一个发现序号和一个 low-link 值，后者是从它的子树出发、至多经由一条指向仍在栈上结点的回边所能抵达的最小序号。结点在被访问时压入栈中。当某个结点结束时其 low-link 等于自身序号，它就是一个分量的根，栈中位于它之上的全部结点连同它一起被弹出，构成该分量。

Tarjan 算法和 Kosaraju 算法有什么区别？

两者都能以 O(V + E) 找出强连通分量。Tarjan 用一次 DFS 配合 low-link 记账和一个栈。Kosaraju 用两趟 DFS，一趟在原图上得到完成时间，一趟在转置图上按完成时间递减的顺序进行。Kosaraju 更好讲解；Tarjan 在实践中更快，因为它无需构造转置图，也只遍历一次。

Tarjan 强连通分量算法的时间复杂度是多少？

O(V + E) 时间和 O(V) 空间。每个结点访问一次，每条边检查一次，每个结点恰好压栈一次、弹栈一次。这是最优的，因为任何算法都必须把整个图读一遍。

强连通分量有什么用途？

把有向图缩成一个 DAG，这是求解 2-SAT 的第一步。此外还用于编译器中的调用图分析与死代码消除、死锁检测、在包管理器与电子表格中找出相互依赖，以及有向社交网络中的社区结构分析。