SCC · condensation

SCC：Tarjan 与 Kosaraju

有向图里若 $u$ 能到 $v$ 、 $v$ 也能到 $u$ ，就把这两个点归作一组。这样分出的每一组叫作一个 strongly connected component，简称 SCC。本页讲它的判定、两种线性算法的对照，以及缩点之后能接上什么。

整个系列共用的工具只有一件：一遍 DFS，每个点记两个整数。同一件工具换到无向图上原样成立，那是 articulation point 与 bridge 一页的内容；而 2-SAT：归约成 SCC 判定把本页的算法整个当子程序调用，连本页给出的分量编号都被那边当作取值规则用。

1 · 互相可达的等价类

定义 1.1（strongly connected component） 有向图 $G = (V, E)$ 上定义 $u \sim v$ 为「 $u$ 可达 $v$ ，且 $v$ 可达 $u$ 」。该关系自反、对称、传递，故为等价关系；每个等价类在 $G$ 中导出的子图称作一个 strongly connected component。

等价关系这一点决定了划分唯一：SCC 与搜索从哪个点起手无关，也与邻接表的顺序无关。不同算法因而可以互相验证，本系列的测试就是这么写的：Tarjan、Kosaraju 与一份 $O(V^3)$ 的传递闭包，三者的划分逐图比对。

把每个 SCC 缩成一个点、丢掉分量内部的边、分量之间的重边只留一条，得到的图叫作 condensation。它必定无环：若缩点后存在有向环，环上两个分量里的点便互相可达，按定义 1.1 它们本该属于同一个分量。原图的宏观结构因而永远是一张 DAG，拓扑排序：Kahn 与 DFS 的结论可以直接接上去。

2 · 时间戳与回溯值

DFS 给每个点记两个整数。dfn 是访问时刻，第几个进入递归就记几。low 取遍这个点的 DFS 子树：从子树里任一点出发，沿至多一条非树边跳一次，所能落到的点中最小的 dfn。

判据只有一行： $\mathrm{low}[u] = \mathrm{dfn}[u]$ 当且仅当 $u$ 是它所在分量中最早被访问的那个点。理由在两个方向上： $u$ 的分量里其余的点都在 $u$ 的子树内，它们的回溯至多回到 $u$ ；而若 $u$ 的子树能跳到一个更早的点 $w$ ， $w$ 又能顺着 DFS 树走回 $u$ ，那么 $u$ 与 $w$ 同属一个分量， $u$ 就不是最早的那个。

分量的根一旦确认，它的整个分量就在栈上连成一段：从栈顶弹到 $u$ 为止，弹出的正好是一个 SCC。

图 2-1 · Tarjan 的单步执行。节点下方是 dfn/low 两个数，栈里留着分量尚未定案的点；可切换图形，观察 low 沿 DFS 树回传的时刻与整个分量出栈的时刻。

3 · 栈上与栈外

栈里放的是「已访问、但分量尚未定案」的点。遇到一条指向已访问点 $v$ 的边时，只有 $v$ 仍在栈上， $\mathrm{dfn}[v]$ 才允许参与 $\mathrm{low}[u]$ 的更新。

警示 · 指向已完成分量的边必须跳过。这类边在无向图里不存在，是有向图独有的第三种情形： $v$ 已访问、却不在栈上。若省掉这个判断， $u$ 会把一个早已定案的分量的 dfn 抄成自己的回溯值， $u$ 所在分量的根从此认不出自己。

第一张预置图的 11 条边里，真正走到这一分支的只有 $F \to G$ 一条，测试对此写死了断言。它的杀伤力可以顺着那张图的实际数值推出来： $\mathrm{dfn}[G] = 5$ ，而 $\mathrm{dfn}[E] = \mathrm{low}[E] = 7$ 。若把 $5$ 记进 $\mathrm{low}[F]$ 再回传， $\mathrm{low}[E]$ 会被压到 $5$ ， $E$ 不再满足 $\mathrm{low} = \mathrm{dfn}$ ， $\lbrace E, F \rbrace$ 这个分量就永远等不到出栈的那一刻。缺陷只在这一条边上暴露，其余十条边一切正常。

另一处常见的手滑是非树边用哪个值：教科书写 $\mathrm{low}[u] \gets \min(\mathrm{low}[u], \mathrm{dfn}[v])$ ，不少实现写成了 $\mathrm{low}[v]$ 。对 SCC 而言这个改动测不出差别，两张预置图加 200 张 seeded 随机图（8 个点、6 至 17 条边）的分量划分逐张一致。同一处改动在无向图上则是致命的，反例见 articulation point 与 bridge §3。测不出反例不等于反例不存在，本页只把实测的范围写清楚。

Tarjan 的代价是每个点进出栈各一次、每条边看一次，合计 $O(V + E)$ 。

4 · 反图与完成序

Kosaraju 换一条路：第一遍在原图上跑 DFS，只记完成序；第二遍在反图上按完成序倒序起手，每棵搜出来的树就是一个 SCC。

成立的理由分两步。反图与原图的 SCC 划分相同，因为互相可达在方向对调后不变。而完成序最靠后的点必落在 condensation 的 source 分量里，从它在反图上出发，走不出本分量的边界：要走出去就得逆着一条 condensation 边，那等于回到 source 的上游，而 source 没有上游。剥掉这个分量后余下的图重复同一论证。

图 4-1 · Kosaraju 的两遍 DFS。第一遍在原图上取完成序，第二遍图会换成反图并按完成序倒序起手；节点下方的编号是它第几个完成。

两种算法都是 $O(V + E)$ ，差别在别处：

	Tarjan	Kosaraju
DFS 遍数	1	2
需要反图	否	是（额外一份邻接表）
每点额外状态	dfn、low、是否在栈上	访问标记 + 完成序数组
产出顺序	condensation 的逆拓扑序	condensation 的拓扑序
实现难点	栈与 onStack 判断	两遍之间的顺序传递

产出顺序的差别可以在第一张预置图上核对：Tarjan 依次弹出 $\lbrace G, H \rbrace$ 、 $\lbrace E, F \rbrace$ 、 $\lbrace B, C, D \rbrace$ 、 $\lbrace A \rbrace$ ，而 Kosaraju 依次扫出 $\lbrace A \rbrace$ 、 $\lbrace B, C, D \rbrace$ 、 $\lbrace E, F \rbrace$ 、 $\lbrace G, H \rbrace$ ，两串恰好相反。

5 · 缩点之后的 DAG

缩点是 SCC 最常见的用途：把一张有向图化成 DAG，剩下的事情交给 DAG 上的算法。分量内部的信息压成一个点的属性（点数、边数、能否走到自己），分量之间只剩单向的依赖。

图 5-1 · 缩点的两张图对照。上图按分量着色，下图是缩点结果，节点下方列出成员；点任一分量可只看它与它的邻边。

Tarjan 的分量编号按出栈先后给，而先出栈的一定是 condensation 里没有出边的那一头，所以编号本身就是一份逆拓扑序。测试逐条边验证了这件事：缩点后每条边都从大编号指向小编号。

注 · 缩点之后不必再跑一次拓扑排序。编号倒过来就是拓扑序，这是 Tarjan 白送的一项性质，Kosaraju 送的则是正向的那一份。2-SAT：归约成 SCC 判定把这项性质直接兑现成取值规则：比较两个分量编号的大小，就是在比较它们在拓扑序上的先后。

6 · 参考文献

Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
Sharir, M. (1981). A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications, 7(1), 67–72.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, §22.5.