企业官网建设流程全解析

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 Components，SCC）：极大的强连通子图。所谓"极大"，意味着不能再向其中加入任何结点而仍然保持强连通。

理解"极大"是区分 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$ 的边可分为四类：

1. 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。所有相邻的树边组成 DFS 生成树。
2. 返祖边（back edge）：也称回边，示意图中以红色边表示（即 $7 \rightarrow 1$），指在搜索过程中，从某个结点指向其祖先结点的非树边。
3. 前向边（forward edge）：示意图中以绿色边表示（即 $3 \rightarrow 6$），指在搜索过程中，从某个结点指向其子树中后代结点的非树边。
4. 横叉边（cross edge）：示意图中以蓝色边表示（即 $9 \rightarrow 7$），指在搜索过程中，从某个结点指向非祖先、非后代且已访问的结点的边，即不属于上述三类的边。

关键性质：SCC 必落在以根为根的子树中

我们考虑 DFS 生成树与强连通分量之间的关系，这是 Tarjan 算法正确性的基石：

如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。

反证法证明：假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中，那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者返祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 $v$ 不在以 $u$ 为根的子树中矛盾了。得证。

该性质意味着：每个 SCC 在 DFS 生成树中都对应一棵"紧凑"的子树，不会出现"SCC 的结点被拆散到子树内外"的情况。这正是"把连通分量看成搜索树中的一棵子树"这一视角的理论来源。

Tarjan 算法求强连通分量

引入：Robert E. Tarjan

Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家。Tarjan 发明了很多算法和数据结构，不少都以他的名字命名，以至于有时会让人混淆几种不同的算法，比如求各种连通分量的 Tarjan 算法、求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法；并查集、Splay、Top tree 也是 Tarjan 发明的。本文要介绍的是在有向图中求强连通分量的 Tarjan 算法，它与无向图中求割点、桥的 Tarjan 算法、求 LCA 的离线 Tarjan 算法是同名异实的三种算法（仓库中求 LCA 的离线 Tarjan 实现见 lca_tarjan.cpp）。

核心变量：dfn 与 low

Tarjan 算法基于对图进行深度优先搜索，把每个连通分量视为搜索树中的一棵子树。搜索过程中维护一个栈，每次把搜索树中尚未处理的节点加入栈中，并将确定下来的答案点从栈中弹出。

为每个结点 $u$ 维护如下两个变量：

1. $\textit{dfn}_u$：深度优先搜索遍历时结点 $u$ 被搜索的次序。
2. $\textit{low}_u$：在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。设在搜索树中以 $u$ 为根的子树为 $\textit{Subtree}_u$，则 $\textit{low}_u$ 定义为以下结点的 $\textit{dfn}$ 的最小值：从 $\textit{Subtree}_u$ 通过一条不在搜索树上的边能到达的在栈中的结点。

由定义可直接推出两条有用的性质：

• 一个结点的子树内结点的 dfn 都大于该结点的 dfn（DFS 先序编号的单调性）。
• 从根开始的一条路径上的 dfn 严格递增，low 严格非降。

直觉上，dfn记录"访问次序"，low记录"最远能回溯到多早"，两者配合即可判定一个结点是否是某个 SCC 的"根"。

算法过程：搜索时的三种情况

按照 DFS 搜索的次序对图中所有结点进行搜索，维护每个结点的dfn与low变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含的结点数目让栈中元素出栈。在搜索过程中，对于结点 $u$ 和与其相邻的结点 $v$（$v$ 不是 $u$ 的父节点）考虑 3 种情况：

1. $v$ 未被访问：继续对 $v$ 进行深度搜索。在回溯过程中，用 $\textit{low}_v$ 更新 $\textit{low}_u$。因为存在从 $u$ 到 $v$ 的直接路径，所以 $v$ 能够回溯到的已经在栈中的结点，$u$ 也一定能够回溯到。
2. $v$ 被访问过，且已经在栈中：根据 low 值的定义，用 $\textit{dfn}_v$ 更新 $\textit{low}_u$。
3. $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 hasn't 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 // 处理并删除残余的 u

C++ 实现

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 - 1

Python 版本与 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 实现：

1. 第一次 DFS：选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
2. 第二次 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 缩点在竞赛题中的典型套路。

关联算法：双连通分量中的 Tarjan

Tarjan 的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