形式陈述

有向图中，顶点 $u,v$$u,v$ 强连通若 $u\leadsto v$$u⇝v$ 且 $v\leadsto u$$v⇝u$。该关系是等价关系，其等价类称强连通分量（SCC）。把每个 SCC 缩成一个点得到凝聚图，凝聚图必为 DAG。Kosaraju 算法用原图 DFS 完成时间与转置图 DFS；Tarjan 算法用 DFS 编号、low-link 值和栈；二者都在邻接表模型下用 $O(|V|+|E|)$$O(|V|+|E|)$ 时间。

直觉

一个 SCC 内所有状态彼此可回到；不同 SCC 之间的单向关系不能形成环，否则它们本应合并。缩点后复杂循环结构被压成无环骨架。

例子与边界

若有边 $a\to b,b\to a,b\to c$$a\to b,b\to a,b\to c$，则 $\{a,b\}$$\{a,b\}$ 是一个 SCC，$\{c\}$$\{c\}$ 是另一个。无向图的每个连通分量在把边视为双向后就是 SCC，但普通有向可达不是对称关系。Tarjan 的 low-link 只沿 DFS 树边和指向栈内顶点的返边更新，不能对已出栈分量随意取最小编号。SCC 分解唯一，但 DFS 树和输出顺序不唯一。

推论与应用

SCC 用于依赖循环、编译器数据流、模型检查、2-SAT 和图缩点动态规划，是把一般有向图化为 DAG 的标准预处理。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。