尧图网站建设 
OI-wiki 图论专题强连通分量SCC求解指南——Tarjan、Kosaraju 与 Garbow 算法全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文以 OI-wiki 仓库中的 强连通分量文档 为主体系统讲解有向图中强连通分量SCC的定义、三种经典求解算法Tarjan、Kosaraju、Garbow的原理与实现并结合仓库内 2-SAT、双连通分量等模块的源码展示缩点的实际应用。读完本文你将掌握dfn/low的核心思想、两次 DFS 的推导逻辑、双栈判定技巧并能在图论建模中熟练运用缩点成 DAG这一重要工具。强连通分量定义与前置概念在阅读本文之前建议先掌握 OI-wiki 中图论相关概念的基础部分特别是连通相关的定义。该文档中明确指出若一张有向图的节点两两互相可达则称这张图是强连通的strongly connected相应地也有弱连通分量极大弱连通子图与强连通分量极大强连通子图的概念并且在本部分中有向图的连通一般指强连通。由此给出两个核心定义强连通Strongly Connected有向图 $G$ 强连通是指$G$ 中任意两个结点连通。强连通分量Strongly Connected ComponentsSCC极大的强连通子图。所谓极大意味着不能再向其中加入任何结点而仍然保持强连通。理解极大是区分 SCC 与一般强连通子图的关键一个 SCC 内部任意两点互相可达且它是包含这些点所能达到的最大集合。求 SCC 的过程本质上就是对有向图做一次结点分组把互相可达的结点归为同一组。DFS 生成树与有向图的四类边三种主流 SCC 算法Tarjan、Kosaraju、Garbow都建立在**深度优先搜索DFS**之上因此先来理解 DFS 在有向图上产生的生成树结构。DFS 的详细讲解可参见 深度优先搜索其文档末尾也明确指出DFS 树有很多性质比如可以用来求强连通分量。DFS 生成树与生成森林在有向图 $G$ 上运行 DFS 算法时由于边具有方向性从单个结点出发可能无法访问到图中的全部结点。因此需要遍历整个顶点集对每个尚未被访问的结点都重新发起一次 DFS。在每一次从某个起始结点出发并完成的 DFS 过程中其所经过的树边会构成一棵树称为DFS 生成树当所有结点都被访问后得到的 DFS 生成树的全体构成了该有向图的DFS 生成森林。需要注意的是生成树以及生成森林的具体结构以及下文的边分类都依赖于 DFS 的起始结点选择和邻接点的访问顺序。这意味着同一条边在不同 DFS 次序下可能被归为不同类别但算法的正确性不依赖于此。有向图的四类边以仓库中的示意图 dfs-tree.svg 为例黑色为树边红色为返祖边 $7 \rightarrow 1$绿色为前向边 $3 \rightarrow 6$蓝色为横叉边 $9 \rightarrow 7$有向图 $G$ 的边可分为四类树边tree edge示意图中以黑色边表示每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。所有相邻的树边组成 DFS 生成树。返祖边back edge也称回边示意图中以红色边表示即 $7 \rightarrow 1$指在搜索过程中从某个结点指向其祖先结点的非树边。前向边forward edge示意图中以绿色边表示即 $3 \rightarrow 6$指在搜索过程中从某个结点指向其子树中后代结点的非树边。横叉边cross edge示意图中以蓝色边表示即 $9 \rightarrow 7$指在搜索过程中从某个结点指向非祖先、非后代且已访问的结点的边即不属于上述三类的边。关键性质SCC 必落在以根为根的子树中我们考虑 DFS 生成树与强连通分量之间的关系这是 Tarjan 算法正确性的基石如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。反证法证明假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者返祖边然而这两条边都要求指向的结点已经被访问过了这就和 $v$ 不在以 $u$ 为根的子树中矛盾了。得证。该性质意味着每个 SCC 在 DFS 生成树中都对应一棵紧凑的子树不会出现SCC 的结点被拆散到子树内外的情况。这正是把连通分量看成搜索树中的一棵子树这一视角的理论来源。Tarjan 算法求强连通分量引入Robert E. TarjanRobert E. Tarjan罗伯特·塔扬1948~生于美国加州波莫纳计算机科学家。Tarjan 发明了很多算法和数据结构不少都以他的名字命名以至于有时会让人混淆几种不同的算法比如求各种连通分量的 Tarjan 算法、求 LCALowest Common Ancestor最近公共祖先的 Tarjan 算法并查集、Splay、Top tree 也是 Tarjan 发明的。本文要介绍的是在有向图中求强连通分量的 Tarjan 算法它与无向图中求割点、桥的 Tarjan 算法、求 LCA 的离线 Tarjan 算法是同名异实的三种算法仓库中求 LCA 的离线 Tarjan 实现见 lca_tarjan.cpp。核心变量dfn 与 lowTarjan 算法基于对图进行深度优先搜索把每个连通分量视为搜索树中的一棵子树。搜索过程中维护一个栈每次把搜索树中尚未处理的节点加入栈中并将确定下来的答案点从栈中弹出。为每个结点 $u$ 维护如下两个变量$\textit{dfn}_u$深度优先搜索遍历时结点 $u$ 被搜索的次序。$\textit{low}_u$在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。设在搜索树中以 $u$ 为根的子树为 $\textit{Subtree}_u$则 $\textit{low}_u$ 定义为以下结点的 $\textit{dfn}$ 的最小值从 $\textit{Subtree}_u$ 通过一条不在搜索树上的边能到达的在栈中的结点。由定义可直接推出两条有用的性质一个结点的子树内结点的 dfn 都大于该结点的 dfnDFS 先序编号的单调性。从根开始的一条路径上的 dfn 严格递增low 严格非降。直觉上dfn记录访问次序low记录最远能回溯到多早两者配合即可判定一个结点是否是某个 SCC 的根。算法过程搜索时的三种情况按照 DFS 搜索的次序对图中所有结点进行搜索维护每个结点的dfn与low变量且让搜索到的结点入栈。每当找到一个强连通元素就按照该元素包含的结点数目让栈中元素出栈。在搜索过程中对于结点 $u$ 和与其相邻的结点 $v$$v$ 不是 $u$ 的父节点考虑 3 种情况$v$ 未被访问继续对 $v$ 进行深度搜索。在回溯过程中用 $\textit{low}_v$ 更新 $\textit{low}_u$。因为存在从 $u$ 到 $v$ 的直接路径所以 $v$ 能够回溯到的已经在栈中的结点$u$ 也一定能够回溯到。$v$ 被访问过且已经在栈中根据 low 值的定义用 $\textit{dfn}_v$ 更新 $\textit{low}_u$。$v$ 被访问过但已不在栈中说明 $v$ 已搜索完毕其所在连通分量已被处理所以不用对其做操作。判定条件dfn[u] low[u]对于一个连通分量图可以证明在该连通图中有且仅有一个 $u$ 使得 $\textit{dfn}_u \textit{low}_u$。该结点一定是在深度遍历的过程中该连通分量中第一个被访问过的结点因为它的 dfn 和 low 值最小不会被该连通分量中的其他结点所影响。因此在回溯的过程中判定 $\textit{dfn}_u \textit{low}_u$ 是否成立如果成立则栈中 $u$及其上方的所有结点构成一个 SCC。将上述算法写成伪代码TARJAN_SEARCH(int u) vis[u]true low[u]dfn[u]dfncnt push u to the stack for each (u,v) then do if v hasnt been searched then TARJAN_SEARCH(v) // 搜索 low[u]min(low[u],low[v]) // 回溯 else if v has been in the stack then low[u]min(low[u],dfn[v]) if dfn[u] equal to low[u] then scccnt while top of stack not equal to u then scc[top of stack] scccnt pop stack scc[u] scccnt pop stack // 处理并删除残余的 uC 实现int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp; int scc[N], sc; // 结点 i 所在 SCC 的编号 int sz[N]; // 强连通 i 的大小 void tarjan(int u) { low[u] dfn[u] dfncnt, s[tp] u, in_stack[u] 1; for (int i h[u]; i; i e[i].nex) { const int v e[i].t; if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (in_stack[v]) { low[u] min(low[u], dfn[v]); } } if (dfn[u] low[u]) { sc; do { scc[s[tp]] sc; sz[sc]; in_stack[s[tp]] 0; } while (s[tp--] ! u); } }实现要点图采用链式前向星存储h为头指针数组e[i].nex/e[i].t分别为下一条边与边的终点这也是 OI 竞赛中最常用的存图方式具体可参见图的存储。s数组充当手写栈tp为栈顶指针in_stack数组用于 O(1) 判断某结点是否仍在栈中对应上文三种情况中的第 2、3 种分支。弹出时用do...while循环保证结点u本身也被弹出入栈sz[sc]同步累加记录每个 SCC 的大小scc[i]记录结点 $i$ 所属的 SCC 编号即染色。Python 实现dfn [0] * N low [0] * N dfncnt 0 s [0] * N in_stack [0] * N tp 0 scc [0] * N sc 0 # 结点 i 所在 SCC 的编号 sz [0] * N # 强连通 i 的大小 def tarjan(u): low[u] dfn[u] dfncnt s[tp] u in_stack[u] 1 dfncnt dfncnt 1 tp tp 1 i h[u] while i: v e[i].t if dfn[v] False: tarjan(v) low[u] min(low[u], low[v]) elif in_stack[v]: low[u] min(low[u], dfn[v]) i e[i].nex if dfn[u] low[u]: sc sc 1 while s[tp] ! u: scc[s[tp]] sc sz[sc] sz[sc] 1 in_stack[s[tp]] 0 tp tp - 1 scc[s[tp]] sc sz[sc] sz[sc] 1 in_stack[s[tp]] 0 tp tp - 1Python 版本与 C 版本逻辑一一对应dfncnt、tp、sc等计数器通过逐行自增显式维护避免使用全局变量声明。使用前需根据实际点数初始化数组长度N以及邻接表h/e。Tarjan 算法的时间复杂度为 $O(n m)$$n$ 为点数$m$ 为边数每个结点至多入栈、出栈一次每条边至多被检查一次空间复杂度为 $O(n)$。分量标号和拓扑序的关系这是一个高频考点务必理清Tarjan 算法在处理过程中实际上是按照某种逆拓扑序来发现强连通分量的这是因为算法在深度优先搜索的过程中会先访问完那些没有出边的节点而这与拓扑排序的过程是相反的。如果我们将图中的所有强连通分量缩成单个节点那么在这些缩点后的节点形成的 DAG 中进行拓扑排序得到的顺序将与 Tarjan 算法给出的强连通分量的标号顺序相反。因此可以说在缩点后的 DAG 中强连通分量缩点后的标号顺序是其拓扑序的逆序。但要注意这种说法仅在考虑了强连通分量之间的依赖关系即从一个强连通分量到另一个强连通分量的有向边时才成立。单个强连通分量内部的节点由于存在环并不满足拓扑序的定义。这一性质的直接应用出现在 2-SAT 问题中见下文缩点与典型应用小节利用Tarjan 求得的 SCC 编号相当于反拓扑序可以在不额外拓扑排序的情况下直接判定可行解并输出方案。Kosaraju 算法引入Kosaraju 算法最早在 1978 年由 S. Rao Kosaraju 在一篇未发表的论文上提出但 Micha Sharir 最早发表了它。它思路直观、证明简洁是理解SCC 与反图关系的绝佳教材缺点是比 Tarjan 多一次完整 DFS。过程两次 DFS该算法依靠两次简单的 DFS 实现第一次 DFS选取任意顶点作为起点遍历所有未访问过的顶点并在回溯之前给顶点编号也就是后序遍历。第二次 DFS对于反向后的图把每条有向边 $u \to v$ 换成 $v \to u$以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点选取标号最大的重复上述过程。两次 DFS 结束后强连通分量就找出来了Kosaraju 算法的时间复杂度为 $O(n m)$。理解要点在反图上从最晚完成的结点出发能到达的所有结点恰好构成原图中的一个 SCC。这是因为原图中若 $u, v$ 互相可达则它们在第一次 DFS 中的完成时间顺序有确定规律反图上的可达性刚好把这些互相可达的结点圈在一起。C 实现// g 是原图g2 是反图 void dfs1(int u) { vis[u] true; for (int v : g[u]) if (!vis[v]) dfs1(v); s.push_back(u); } void dfs2(int u) { color[u] sccCnt; for (int v : g2[u]) if (!color[v]) dfs2(v); } void kosaraju() { sccCnt 0; for (int i 1; i n; i) if (!vis[i]) dfs1(i); for (int i n - 1; i 0; --i) if (!color[s[i]]) { sccCnt; dfs2(s[i]); } }实现要点dfs1在原图g上做后序遍历完成顺序存入s此时s的末尾是最晚完成的结点。dfs2在反图g2上按完成时间从晚到早即s从后往前染色color[u]即结点 $u$ 的 SCC 编号sccCnt记录分量总数。注意第二次 DFS 的循环方向i n - 1; i 0; --i对应选取标号最大的结点这一规则。Python 实现def dfs1(u): vis[u] True for v in g[u]: if vis[v] False: dfs1(v) s.append(u) def dfs2(u): color[u] sccCnt for v in g2[u]: if color[v] False: dfs2(v) def kosaraju(u): sccCnt 0 for i in range(1, n 1): if vis[i] False: dfs1(i) for i in range(n - 1, -1, -1): if color[s[i]] False: sccCnt sccCnt 1 dfs2(s[i])Kosaraju 的实现比 Tarjan 更无脑只要会写 DFS 就会写 Kosaraju代价是需要额外存储一张反图空间开销约为 Tarjan 的两倍两份邻接表。Garbow 算法过程双栈判定Garbow 算法是Tarjan 算法的另一种实现Tarjan 算法用 dfn 和 low 来计算强连通分量的根而 Garbow 维护一个节点栈并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点。具体过程如下从节点 $w$ 开始的 DFS 过程中当一条路径显示这组节点都属于同一个强连通分量时只要栈顶节点的访问时间大于根节点 $w$ 的访问时间就从第二个栈中弹出这个节点最后只留下根节点 $w$。在这个过程中每一个被弹出的节点都属于同一个强连通分量。当回溯到某一个节点 $w$ 时如果这个节点在第二个栈的顶部就说明这个节点是强连通分量的起始节点在这个节点之后搜索到的那些节点都属于同一个强连通分量于是从第一个栈中弹出那些节点构成强连通分量。直觉上第二个栈始终保留当前尚未确定归属的分量候选根第一个栈则按 DFS 顺序累积所有尚未归类的结点每当第二个栈顶回到 $w$ 自身就说明 $w$ 之后入栈的结点全部与 $w$ 互相可达可以一次性弹出打包成一个 SCC。C 实现int garbow(int u) { stack1[p1] u; stack2[p2] u; low[u] dfs_clock; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (!low[v]) garbow(v); else if (!sccno[v]) while (low[stack2[p2]] low[v]) p2--; } if (stack2[p2] u) { p2--; scc_cnt; do { sccno[stack1[p1]] scc_cnt; // all_scc[scc_cnt] ; } while (stack1[p1--] ! u); } return 0; } void find_scc(int n) { dfs_clock scc_cnt 0; p1 p2 0; memset(sccno, 0, sizeof(sccno)); memset(low, 0, sizeof(low)); for (int i 1; i n; i) if (!low[i]) garbow(i); }Python 实现def garbow(u): stack1[p1] u stack2[p2] u p1 p1 1 p2 p2 1 low[u] dfs_clock dfs_clock dfs_clock 1 i head[u] while i: v e[i].to if low[v] False: garbow(v) elif sccno[v] False: while low[stack2[p2]] low[v]: p2 p2 - 1 if stack2[p2] u: p2 p2 - 1 scc_cnt scc_cnt 1 while stack1[p1] ! u: p1 p1 - 1 sccno[stack1[p1]] scc_cnt def find_scc(n): dfs_clock scc_cnt 0 p1 p2 0 sccno [] low [] for i in range(1, n 1): if low[i] False: garbow(i)Garbow 与 Tarjan 的时间复杂度同为 $O(n m)$区别只在于用第二栈取代了比较dfn low这一显式判定代码风格更贴近栈操作的原始直觉。三者中 Tarjan 因只需一次 DFS 且无需反图在 OI 中最为常用。缩点与典型应用缩点把有向图变成 DAG求 SCC 最重要的应用是缩点condensation我们可以将一张图的每个强连通分量都缩成一个点。由于强连通分量内部任意两点互相可达缩点后得到的图变成了一个DAG有向无环图从而可以进行拓扑排序以及更多其他操作最长路、DP、支配等。仓库中 2-SAT 文档 的一段描述直接说明了这一思想的威力建图后我们使用 Tarjan 算法找 SCC判断对于任意布尔变量 $a$表示 $a$ 成立的点和表示 $a$ 不成立的点是否在同一个 SCC 中……输出方案时可以通过变量在图中的拓扑序确定该变量的取值。应用到 Tarjan 算法的缩点即 $x$ 所在 SCC 编号在 $\neg x$ 之前时取 $x$ 为真。因为 Tarjan 算法求强连通分量时使用了栈……所以 Tarjan 求得的 SCC 编号相当于反拓扑序。对应的完整实现见 2-sat_1.cpp其中tarjan函数以color[sta[top]] tot的方式给结点染色编号正是本文 Tarjan 实现的实战形态solve()中if (color[i] color[i 1]) return false;即利用同一变量与其否定在同一 SCC 则无解的判定。应用举例经过重复结点的最长不同结点路径举个简单的例子求一条路径可以经过重复结点要求经过的不同结点数量最多。做法是利用缩点后的 DAG同一 SCC 内的结点可以互相到达因此只要路径进入某个 SCC就能免费访问其中全部结点重复经过不算多。于是问题转化为在缩点后的 DAG 上做带权的最长路DP——每个缩点的权值即其内部结点数对应 Tarjan 实现中的sz[sc]。这是 SCC 缩点在竞赛题中的典型套路。关联算法双连通分量中的 TarjanTarjan 的dfn/low思想不止适用于有向图的强连通分量。在无向图的双连通分量问题中边双连通分量文档 明确指出用 Tarjan 求双连通分量过程与求强连通分量类似并总结出一条漂亮的对应关系求无向图边双连通分量的过程实际上就是求强连通分量的过程——只要把无向边视作两条有向边、用父边规避回退即可。仓库中 bcc_1.cpp、bcc_2.cpp、bcc_3.cpp 分别给出了先求桥再 DFS直接仿 SCC 双栈求点双连通分量三种完整可运行的实现其中dfn[u] low[u]的判定结构与本文 Tarjan 代码一脉相承。割点、桥的详细讨论可参见 割点和桥。习题练习通过以下经典题目巩固三种算法的理解与缩点技巧USACO Fall/HAOI 2006 受欢迎的牛洛谷 P2341 / LOJ 10091考察缩点后出度为 0 的分量这一经典结论。POJ 1236 Network of Schools考察最少需要多少起点才能到达全部结点与最少加几条边使图强连通两者分别对应缩点后 DAG 的入度为 0 与出度为 0 的分量个数。建议按先手写 Tarjan 的 dfn/low 流程 → 再实现 Kosaraju 的双 DFS → 最后对比 Garbow 双栈写法的顺序练习并尝试用缩点思想把每道题转化为 DAG 上的问题即可彻底掌握强连通分量这一图论基础工具。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 图论专题：强连通分量（SCC）求解指南——Tarjan、Kosaraju 与 Garbow 算法全解析
OI-wiki 图论专题强连通分量SCC求解指南——Tarjan、Kosaraju 与 Garbow 算法全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文以 OI-wiki 仓库中的 强连通分量文档 为主体系统讲解有向图中强连通分量SCC的定义、三种经典求解算法Tarjan、Kosaraju、Garbow的原理与实现并结合仓库内 2-SAT、双连通分量等模块的源码展示缩点的实际应用。读完本文你将掌握dfn/low的核心思想、两次 DFS 的推导逻辑、双栈判定技巧并能在图论建模中熟练运用缩点成 DAG这一重要工具。强连通分量定义与前置概念在阅读本文之前建议先掌握 OI-wiki 中图论相关概念的基础部分特别是连通相关的定义。该文档中明确指出若一张有向图的节点两两互相可达则称这张图是强连通的strongly connected相应地也有弱连通分量极大弱连通子图与强连通分量极大强连通子图的概念并且在本部分中有向图的连通一般指强连通。由此给出两个核心定义强连通Strongly Connected有向图 $G$ 强连通是指$G$ 中任意两个结点连通。强连通分量Strongly Connected ComponentsSCC极大的强连通子图。所谓极大意味着不能再向其中加入任何结点而仍然保持强连通。理解极大是区分 SCC 与一般强连通子图的关键一个 SCC 内部任意两点互相可达且它是包含这些点所能达到的最大集合。求 SCC 的过程本质上就是对有向图做一次结点分组把互相可达的结点归为同一组。DFS 生成树与有向图的四类边三种主流 SCC 算法Tarjan、Kosaraju、Garbow都建立在**深度优先搜索DFS**之上因此先来理解 DFS 在有向图上产生的生成树结构。DFS 的详细讲解可参见 深度优先搜索其文档末尾也明确指出DFS 树有很多性质比如可以用来求强连通分量。DFS 生成树与生成森林在有向图 $G$ 上运行 DFS 算法时由于边具有方向性从单个结点出发可能无法访问到图中的全部结点。因此需要遍历整个顶点集对每个尚未被访问的结点都重新发起一次 DFS。在每一次从某个起始结点出发并完成的 DFS 过程中其所经过的树边会构成一棵树称为DFS 生成树当所有结点都被访问后得到的 DFS 生成树的全体构成了该有向图的DFS 生成森林。需要注意的是生成树以及生成森林的具体结构以及下文的边分类都依赖于 DFS 的起始结点选择和邻接点的访问顺序。这意味着同一条边在不同 DFS 次序下可能被归为不同类别但算法的正确性不依赖于此。有向图的四类边以仓库中的示意图 dfs-tree.svg 为例黑色为树边红色为返祖边 $7 \rightarrow 1$绿色为前向边 $3 \rightarrow 6$蓝色为横叉边 $9 \rightarrow 7$有向图 $G$ 的边可分为四类树边tree edge示意图中以黑色边表示每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。所有相邻的树边组成 DFS 生成树。返祖边back edge也称回边示意图中以红色边表示即 $7 \rightarrow 1$指在搜索过程中从某个结点指向其祖先结点的非树边。前向边forward edge示意图中以绿色边表示即 $3 \rightarrow 6$指在搜索过程中从某个结点指向其子树中后代结点的非树边。横叉边cross edge示意图中以蓝色边表示即 $9 \rightarrow 7$指在搜索过程中从某个结点指向非祖先、非后代且已访问的结点的边即不属于上述三类的边。关键性质SCC 必落在以根为根的子树中我们考虑 DFS 生成树与强连通分量之间的关系这是 Tarjan 算法正确性的基石如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。反证法证明假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者返祖边然而这两条边都要求指向的结点已经被访问过了这就和 $v$ 不在以 $u$ 为根的子树中矛盾了。得证。该性质意味着每个 SCC 在 DFS 生成树中都对应一棵紧凑的子树不会出现SCC 的结点被拆散到子树内外的情况。这正是把连通分量看成搜索树中的一棵子树这一视角的理论来源。Tarjan 算法求强连通分量引入Robert E. TarjanRobert E. Tarjan罗伯特·塔扬1948~生于美国加州波莫纳计算机科学家。Tarjan 发明了很多算法和数据结构不少都以他的名字命名以至于有时会让人混淆几种不同的算法比如求各种连通分量的 Tarjan 算法、求 LCALowest Common Ancestor最近公共祖先的 Tarjan 算法并查集、Splay、Top tree 也是 Tarjan 发明的。本文要介绍的是在有向图中求强连通分量的 Tarjan 算法它与无向图中求割点、桥的 Tarjan 算法、求 LCA 的离线 Tarjan 算法是同名异实的三种算法仓库中求 LCA 的离线 Tarjan 实现见 lca_tarjan.cpp。核心变量dfn 与 lowTarjan 算法基于对图进行深度优先搜索把每个连通分量视为搜索树中的一棵子树。搜索过程中维护一个栈每次把搜索树中尚未处理的节点加入栈中并将确定下来的答案点从栈中弹出。为每个结点 $u$ 维护如下两个变量$\textit{dfn}_u$深度优先搜索遍历时结点 $u$ 被搜索的次序。$\textit{low}_u$在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。设在搜索树中以 $u$ 为根的子树为 $\textit{Subtree}_u$则 $\textit{low}_u$ 定义为以下结点的 $\textit{dfn}$ 的最小值从 $\textit{Subtree}_u$ 通过一条不在搜索树上的边能到达的在栈中的结点。由定义可直接推出两条有用的性质一个结点的子树内结点的 dfn 都大于该结点的 dfnDFS 先序编号的单调性。从根开始的一条路径上的 dfn 严格递增low 严格非降。直觉上dfn记录访问次序low记录最远能回溯到多早两者配合即可判定一个结点是否是某个 SCC 的根。算法过程搜索时的三种情况按照 DFS 搜索的次序对图中所有结点进行搜索维护每个结点的dfn与low变量且让搜索到的结点入栈。每当找到一个强连通元素就按照该元素包含的结点数目让栈中元素出栈。在搜索过程中对于结点 $u$ 和与其相邻的结点 $v$$v$ 不是 $u$ 的父节点考虑 3 种情况$v$ 未被访问继续对 $v$ 进行深度搜索。在回溯过程中用 $\textit{low}_v$ 更新 $\textit{low}_u$。因为存在从 $u$ 到 $v$ 的直接路径所以 $v$ 能够回溯到的已经在栈中的结点$u$ 也一定能够回溯到。$v$ 被访问过且已经在栈中根据 low 值的定义用 $\textit{dfn}_v$ 更新 $\textit{low}_u$。$v$ 被访问过但已不在栈中说明 $v$ 已搜索完毕其所在连通分量已被处理所以不用对其做操作。判定条件dfn[u] low[u]对于一个连通分量图可以证明在该连通图中有且仅有一个 $u$ 使得 $\textit{dfn}_u \textit{low}_u$。该结点一定是在深度遍历的过程中该连通分量中第一个被访问过的结点因为它的 dfn 和 low 值最小不会被该连通分量中的其他结点所影响。因此在回溯的过程中判定 $\textit{dfn}_u \textit{low}_u$ 是否成立如果成立则栈中 $u$及其上方的所有结点构成一个 SCC。将上述算法写成伪代码TARJAN_SEARCH(int u) vis[u]true low[u]dfn[u]dfncnt push u to the stack for each (u,v) then do if v hasnt been searched then TARJAN_SEARCH(v) // 搜索 low[u]min(low[u],low[v]) // 回溯 else if v has been in the stack then low[u]min(low[u],dfn[v]) if dfn[u] equal to low[u] then scccnt while top of stack not equal to u then scc[top of stack] scccnt pop stack scc[u] scccnt pop stack // 处理并删除残余的 uC 实现int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp; int scc[N], sc; // 结点 i 所在 SCC 的编号 int sz[N]; // 强连通 i 的大小 void tarjan(int u) { low[u] dfn[u] dfncnt, s[tp] u, in_stack[u] 1; for (int i h[u]; i; i e[i].nex) { const int v e[i].t; if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (in_stack[v]) { low[u] min(low[u], dfn[v]); } } if (dfn[u] low[u]) { sc; do { scc[s[tp]] sc; sz[sc]; in_stack[s[tp]] 0; } while (s[tp--] ! u); } }实现要点图采用链式前向星存储h为头指针数组e[i].nex/e[i].t分别为下一条边与边的终点这也是 OI 竞赛中最常用的存图方式具体可参见图的存储。s数组充当手写栈tp为栈顶指针in_stack数组用于 O(1) 判断某结点是否仍在栈中对应上文三种情况中的第 2、3 种分支。弹出时用do...while循环保证结点u本身也被弹出入栈sz[sc]同步累加记录每个 SCC 的大小scc[i]记录结点 $i$ 所属的 SCC 编号即染色。Python 实现dfn [0] * N low [0] * N dfncnt 0 s [0] * N in_stack [0] * N tp 0 scc [0] * N sc 0 # 结点 i 所在 SCC 的编号 sz [0] * N # 强连通 i 的大小 def tarjan(u): low[u] dfn[u] dfncnt s[tp] u in_stack[u] 1 dfncnt dfncnt 1 tp tp 1 i h[u] while i: v e[i].t if dfn[v] False: tarjan(v) low[u] min(low[u], low[v]) elif in_stack[v]: low[u] min(low[u], dfn[v]) i e[i].nex if dfn[u] low[u]: sc sc 1 while s[tp] ! u: scc[s[tp]] sc sz[sc] sz[sc] 1 in_stack[s[tp]] 0 tp tp - 1 scc[s[tp]] sc sz[sc] sz[sc] 1 in_stack[s[tp]] 0 tp tp - 1Python 版本与 C 版本逻辑一一对应dfncnt、tp、sc等计数器通过逐行自增显式维护避免使用全局变量声明。使用前需根据实际点数初始化数组长度N以及邻接表h/e。Tarjan 算法的时间复杂度为 $O(n m)$$n$ 为点数$m$ 为边数每个结点至多入栈、出栈一次每条边至多被检查一次空间复杂度为 $O(n)$。分量标号和拓扑序的关系这是一个高频考点务必理清Tarjan 算法在处理过程中实际上是按照某种逆拓扑序来发现强连通分量的这是因为算法在深度优先搜索的过程中会先访问完那些没有出边的节点而这与拓扑排序的过程是相反的。如果我们将图中的所有强连通分量缩成单个节点那么在这些缩点后的节点形成的 DAG 中进行拓扑排序得到的顺序将与 Tarjan 算法给出的强连通分量的标号顺序相反。因此可以说在缩点后的 DAG 中强连通分量缩点后的标号顺序是其拓扑序的逆序。但要注意这种说法仅在考虑了强连通分量之间的依赖关系即从一个强连通分量到另一个强连通分量的有向边时才成立。单个强连通分量内部的节点由于存在环并不满足拓扑序的定义。这一性质的直接应用出现在 2-SAT 问题中见下文缩点与典型应用小节利用Tarjan 求得的 SCC 编号相当于反拓扑序可以在不额外拓扑排序的情况下直接判定可行解并输出方案。Kosaraju 算法引入Kosaraju 算法最早在 1978 年由 S. Rao Kosaraju 在一篇未发表的论文上提出但 Micha Sharir 最早发表了它。它思路直观、证明简洁是理解SCC 与反图关系的绝佳教材缺点是比 Tarjan 多一次完整 DFS。过程两次 DFS该算法依靠两次简单的 DFS 实现第一次 DFS选取任意顶点作为起点遍历所有未访问过的顶点并在回溯之前给顶点编号也就是后序遍历。第二次 DFS对于反向后的图把每条有向边 $u \to v$ 换成 $v \to u$以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点选取标号最大的重复上述过程。两次 DFS 结束后强连通分量就找出来了Kosaraju 算法的时间复杂度为 $O(n m)$。理解要点在反图上从最晚完成的结点出发能到达的所有结点恰好构成原图中的一个 SCC。这是因为原图中若 $u, v$ 互相可达则它们在第一次 DFS 中的完成时间顺序有确定规律反图上的可达性刚好把这些互相可达的结点圈在一起。C 实现// g 是原图g2 是反图 void dfs1(int u) { vis[u] true; for (int v : g[u]) if (!vis[v]) dfs1(v); s.push_back(u); } void dfs2(int u) { color[u] sccCnt; for (int v : g2[u]) if (!color[v]) dfs2(v); } void kosaraju() { sccCnt 0; for (int i 1; i n; i) if (!vis[i]) dfs1(i); for (int i n - 1; i 0; --i) if (!color[s[i]]) { sccCnt; dfs2(s[i]); } }实现要点dfs1在原图g上做后序遍历完成顺序存入s此时s的末尾是最晚完成的结点。dfs2在反图g2上按完成时间从晚到早即s从后往前染色color[u]即结点 $u$ 的 SCC 编号sccCnt记录分量总数。注意第二次 DFS 的循环方向i n - 1; i 0; --i对应选取标号最大的结点这一规则。Python 实现def dfs1(u): vis[u] True for v in g[u]: if vis[v] False: dfs1(v) s.append(u) def dfs2(u): color[u] sccCnt for v in g2[u]: if color[v] False: dfs2(v) def kosaraju(u): sccCnt 0 for i in range(1, n 1): if vis[i] False: dfs1(i) for i in range(n - 1, -1, -1): if color[s[i]] False: sccCnt sccCnt 1 dfs2(s[i])Kosaraju 的实现比 Tarjan 更无脑只要会写 DFS 就会写 Kosaraju代价是需要额外存储一张反图空间开销约为 Tarjan 的两倍两份邻接表。Garbow 算法过程双栈判定Garbow 算法是Tarjan 算法的另一种实现Tarjan 算法用 dfn 和 low 来计算强连通分量的根而 Garbow 维护一个节点栈并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点。具体过程如下从节点 $w$ 开始的 DFS 过程中当一条路径显示这组节点都属于同一个强连通分量时只要栈顶节点的访问时间大于根节点 $w$ 的访问时间就从第二个栈中弹出这个节点最后只留下根节点 $w$。在这个过程中每一个被弹出的节点都属于同一个强连通分量。当回溯到某一个节点 $w$ 时如果这个节点在第二个栈的顶部就说明这个节点是强连通分量的起始节点在这个节点之后搜索到的那些节点都属于同一个强连通分量于是从第一个栈中弹出那些节点构成强连通分量。直觉上第二个栈始终保留当前尚未确定归属的分量候选根第一个栈则按 DFS 顺序累积所有尚未归类的结点每当第二个栈顶回到 $w$ 自身就说明 $w$ 之后入栈的结点全部与 $w$ 互相可达可以一次性弹出打包成一个 SCC。C 实现int garbow(int u) { stack1[p1] u; stack2[p2] u; low[u] dfs_clock; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (!low[v]) garbow(v); else if (!sccno[v]) while (low[stack2[p2]] low[v]) p2--; } if (stack2[p2] u) { p2--; scc_cnt; do { sccno[stack1[p1]] scc_cnt; // all_scc[scc_cnt] ; } while (stack1[p1--] ! u); } return 0; } void find_scc(int n) { dfs_clock scc_cnt 0; p1 p2 0; memset(sccno, 0, sizeof(sccno)); memset(low, 0, sizeof(low)); for (int i 1; i n; i) if (!low[i]) garbow(i); }Python 实现def garbow(u): stack1[p1] u stack2[p2] u p1 p1 1 p2 p2 1 low[u] dfs_clock dfs_clock dfs_clock 1 i head[u] while i: v e[i].to if low[v] False: garbow(v) elif sccno[v] False: while low[stack2[p2]] low[v]: p2 p2 - 1 if stack2[p2] u: p2 p2 - 1 scc_cnt scc_cnt 1 while stack1[p1] ! u: p1 p1 - 1 sccno[stack1[p1]] scc_cnt def find_scc(n): dfs_clock scc_cnt 0 p1 p2 0 sccno [] low [] for i in range(1, n 1): if low[i] False: garbow(i)Garbow 与 Tarjan 的时间复杂度同为 $O(n m)$区别只在于用第二栈取代了比较dfn low这一显式判定代码风格更贴近栈操作的原始直觉。三者中 Tarjan 因只需一次 DFS 且无需反图在 OI 中最为常用。缩点与典型应用缩点把有向图变成 DAG求 SCC 最重要的应用是缩点condensation我们可以将一张图的每个强连通分量都缩成一个点。由于强连通分量内部任意两点互相可达缩点后得到的图变成了一个DAG有向无环图从而可以进行拓扑排序以及更多其他操作最长路、DP、支配等。仓库中 2-SAT 文档 的一段描述直接说明了这一思想的威力建图后我们使用 Tarjan 算法找 SCC判断对于任意布尔变量 $a$表示 $a$ 成立的点和表示 $a$ 不成立的点是否在同一个 SCC 中……输出方案时可以通过变量在图中的拓扑序确定该变量的取值。应用到 Tarjan 算法的缩点即 $x$ 所在 SCC 编号在 $\neg x$ 之前时取 $x$ 为真。因为 Tarjan 算法求强连通分量时使用了栈……所以 Tarjan 求得的 SCC 编号相当于反拓扑序。对应的完整实现见 2-sat_1.cpp其中tarjan函数以color[sta[top]] tot的方式给结点染色编号正是本文 Tarjan 实现的实战形态solve()中if (color[i] color[i 1]) return false;即利用同一变量与其否定在同一 SCC 则无解的判定。应用举例经过重复结点的最长不同结点路径举个简单的例子求一条路径可以经过重复结点要求经过的不同结点数量最多。做法是利用缩点后的 DAG同一 SCC 内的结点可以互相到达因此只要路径进入某个 SCC就能免费访问其中全部结点重复经过不算多。于是问题转化为在缩点后的 DAG 上做带权的最长路DP——每个缩点的权值即其内部结点数对应 Tarjan 实现中的sz[sc]。这是 SCC 缩点在竞赛题中的典型套路。关联算法双连通分量中的 TarjanTarjan 的dfn/low思想不止适用于有向图的强连通分量。在无向图的双连通分量问题中边双连通分量文档 明确指出用 Tarjan 求双连通分量过程与求强连通分量类似并总结出一条漂亮的对应关系求无向图边双连通分量的过程实际上就是求强连通分量的过程——只要把无向边视作两条有向边、用父边规避回退即可。仓库中 bcc_1.cpp、bcc_2.cpp、bcc_3.cpp 分别给出了先求桥再 DFS直接仿 SCC 双栈求点双连通分量三种完整可运行的实现其中dfn[u] low[u]的判定结构与本文 Tarjan 代码一脉相承。割点、桥的详细讨论可参见 割点和桥。习题练习通过以下经典题目巩固三种算法的理解与缩点技巧USACO Fall/HAOI 2006 受欢迎的牛洛谷 P2341 / LOJ 10091考察缩点后出度为 0 的分量这一经典结论。POJ 1236 Network of Schools考察最少需要多少起点才能到达全部结点与最少加几条边使图强连通两者分别对应缩点后 DAG 的入度为 0 与出度为 0 的分量个数。建议按先手写 Tarjan 的 dfn/low 流程 → 再实现 Kosaraju 的双 DFS → 最后对比 Garbow 双栈写法的顺序练习并尝试用缩点思想把每道题转化为 DAG 上的问题即可彻底掌握强连通分量这一图论基础工具。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考