1. 写在最前面这玩意儿到底是干嘛的强连通分量英文全称 Strongly Connected Components圈内习惯简写为 SCC。第一次接触图论算法的人看到这个概念脑子里大概率是一团浆糊什么叫“强连通”跟“连通”又差在哪儿最直观的理解方式是这样的。想象一个有向图里的若干节点是一伙人强连通分量就是这样一个“小圈子”圈子里的任何一个人都能沿着有向边找到路走到圈子里的任何一个其他人。注意是有向边这就和普通的无向图连通性彻底拉开了差距。无向图里你只要有一条路能走反过来也能走有向图里你从 A 能到 B并不代表 B 能回到 A。所以强连通分量专门处理的是“互相可达”这种更强的关系。Tarjan 算法就是用来在一张有向图里把所有这些“小圈子”一个不落地找出来的经典算法。它由 Robert Tarjan 在 1972 年提出来用一次深度优先搜索DFS就能搞定时间复杂度 O(VE)空间复杂度也基本是 O(V)。这个效率在同类算法里属于顶级水平和他同时期的 Kosaraju 算法相比省去了“对原图做一遍 DFS、对反图再做一遍 DFS”的两轮遍历而是只靠一套 DFS 流程就同时完成了“发现”和“归类”两个动作。在这个领域里Tarjan 算法几乎是面试和竞赛的必备考点。你在处理“缩点”“2-SAT”“最小环”“必经点”等问题的时候第一步往往就是找 SCC。可以把它理解成高级图论问题的一块地基地基没打牢上面的建筑全白搭。这篇文章就来完整拆解一下这个算法的原理、实现、常见问题和调试技巧全是实操积累的东西。你要是能耐心看到最后一个章节遇到相关题目基本能直接上手写代码。2. 整体设计思路拆解为什么 Tarjan 能一趟 DFS 解决问题2.1 从“搜索树”到“回溯边”的观察初次接触 Tarjan 算法最让人困惑的点是它到底凭什么在一次 DFS 中就能把所有 SCC 找出来核心逻辑藏在 DFS 的过程里。你对一张有向图做深度优先遍历会自然生成一棵“DFS 搜索树”树上的边是实际递归走过的边。但原图里还有一些边是搜索树中没有走过的它们指向已经访问过的节点这些边就是“回溯边”也叫返祖边。强连通分量之所以能形成靠的正是这些回溯边把搜索树上的几条路径“连接”起来形成闭环。举个例子假设从节点 1 开始搜索走到节点 2走到节点 3结果节点 3 有一条边指向节点 1。这样一来节点 1、2、3 就构成了一个环也就是一个完整的 SCC。Tarjan 算法的聪明之处在于它用两个时间戳数组记录 DFS 过程中的关键信息然后根据这些信息判断一个节点能否成为某个 SCC 的“根”。这里强烈建议你拿纸笔手动模拟一遍随便画一张有 7 个节点的有向图按自己的习惯编号然后人工执行一遍 DFS记录每个节点的访问顺序和栈的变化。我当年学这个算法的时候就是靠这样画了五六张图才彻底把逻辑理清楚。只看代码是学不会 Tarjan 的必须亲手模拟。2.2 两个核心数组dfn 和 lowTarjan 算法离不开两个数组分别是 dfn 和 low。dfn[u] 表示节点 u 在 DFS 过程中被首次访问的时间戳也就是访问顺序编号这个编号一旦确定就不会再改变。low[u] 表示节点 u 通过自身的子树内节点和至多一条回溯边能够追溯到的“最早”时间戳。也就是说low[u] 的维护目标是最小化“能到达的、还在栈中的节点”的 dfn 值。这里最重要的限制是“还在栈中”——因为栈里保存的是当前尚未处理完的、可能属于同一个 SCC 的节点集合。如果目标节点已经出栈了说明它已经属于另一个 SCC 了不能再去更新 low 值。每次 DFS 到一个新节点 u先把 dfn[u] 和 low[u] 都初始化为当前时间戳加一然后把 u 压入栈中继续递归访问它的所有邻接节点 v。递归返回后用 low[v] 去更新 low[u]。这里要特别注意区分三种情况对应三种不同的处理方式。第一种情况v 尚未被访问过dfn[v] 为 0这意味着 v 是从 u 出发在搜索树上的子节点那么递归访问 v然后 low[u] min(low[u], low[v])。第二种情况v 已经被访问过而且还在栈中说明 v 是 u 的“祖先”或者“祖先的后代路径上某个尚未处理的节点”此时用 dfn[v] 更新 low[u]low[u] min(low[u], dfn[v])。这里用的不是 low[v]而是 dfn[v]因为这个更新动作针对的是回溯边回溯边的终点是当前搜索树上已经确定编号的节点用 dfn 值来比较最合适。第三种情况v 已经被访问过但已经不在栈中说明 v 属于一个已经确定完成的 SCC这条边对于当前 u 的 low 值没有任何意义直接忽略。2.3 判断根节点的条件与“出栈”操作在 u 的所有邻接节点访问完毕之后如果发现 low[u] 等于 dfn[u]那 u 就是当前这个强连通分量的“根”。为什么因为 low[u] 等于 dfn[u] 意味着什么意味着 u 无法通过子树中的任何节点、任何回溯边追溯到比 u 更早访问的节点。换句话说u 是整个这个小圈子里的“最早祖先”这个圈子的所有节点都在 u 的子树里。这时候就把栈中的节点依次弹出直到弹出 u 为止。所有弹出的节点构成一个完整的 SCC。这里有一个很关键的小细节弹出的过程中你可能先弹出的是后来入栈的节点这些节点的 dfn 值一定大于 u 的 dfn 值它们也就是 u 的子树中的节点。弹到 u 为止说明这条“链”上的所有节点都能互相到达。有人可能会问为什么 low[u] 等于 dfn[u] 就一定意味着 u 是根而不是某个子树节点正好把 low 值同化成 dfn[u]仔细想一下 low 的更新规则就能理解子树里的节点想把 low 值变小必须依赖一条能走到更早节点的路径而要走到比 u 更早的节点必然意味着有一条边从 u 的子树指向 u 的祖先——这种情况下 low[u] 早就在回溯边处理时被更新成更小的值了。所以当 low[u] 保持等于 dfn[u] 的状态就说明它的子树完全“封闭”了再没有任何路径可以逃出这个圈子。3. 核心细节解析与实操要点3.1 为什么栈是算法的灵魂Tarjan 算法的另一大支柱就是那个显式的栈。这个栈的灵魂在于它维护的是“当前还在被处理中的搜索路径上尚未归属任何 SCC 的节点集合”。这个栈和普通 DFS 的系统递归栈有什么区别系统递归栈只记录函数调用链而 Tarjan 的栈记录的是“按访问顺序加入、尚未确定归属”的节点。当一个 SCC 被确定后它的所有节点会一股脑儿弹出去从栈中整体消失。这就意味着栈中任意两个相邻节点之间未必有直接的边连接但它们在访问顺序上是连续的而且它们都在等待被归类到某个 SCC 中。理解这个栈的关键场景是遇到回溯边把 low 值更新到更早的节点。比如节点 6 有一条回溯边指向节点 2那么节点 6 的 low 值会被更新为 dfn[2] 的值。这个值可能比某个中间节点的 low 值小很多从而在后续判断根节点时产生连锁反应。若没有栈来标记哪些节点还在处理中你就没办法区分“一条边指向仍在等待归类的节点”和“一条边指向已经归类完毕的节点”算法逻辑就会出现严重错误。我见过不少人在自己实现 Tarjan 的时候省掉了栈或者用 visited 数组替代结果算出来的 SCC 数量总是偏多。原因就在这儿去了栈就丢了“时间顺序”等于把算法最重要的状态给扔了。3.2 动手模拟一张 8 节点图的完整过程理论讲得再多不如手动推演一遍。下面这张图包含 8 个节点边按以下规则建立1 → 22 → 33 → 13 → 44 → 55 → 66 → 45 → 77 → 88 → 7从节点 1 开始执行 Tarjan 算法。访问 1dfn[1]1, low[1]1入栈栈状态[1]。从 1 走到 2dfn[2]2, low[2]2入栈栈状态[1, 2]。从 2 走到 3dfn[3]3, low[3]3入栈栈状态[1, 2, 3]。节点 3 的邻接节点是 1 和 4。先处理 11 已经在栈中所以 low[3] min(low[3], dfn[1]) min(3, 1) 1。这表示节点 3 可以通过回溯边 3→1 追溯到最早访问的节点 1。接着处理 4dfn[4]4, low[4]4入栈栈状态[1, 2, 3, 4]。从 4 走到 5dfn[5]5, low[5]5入栈栈状态[1, 2, 3, 4, 5]。从 5 走到 6dfn[6]6, low[6]6入栈栈状态[1, 2, 3, 4, 5, 6]。节点 6 的邻接节点是 44 已经在栈中所以 low[6] min(low[6], dfn[4]) min(6, 4) 4。节点 6 处理完毕low[6]4不等于 dfn[6]6所以 6 不是根节点继续回溯到 5。节点 5 的另一个邻接节点是 7。访问 7dfn[7]7, low[7]7入栈栈状态[1, 2, 3, 4, 5, 6, 7]。从 7 走到 8dfn[8]8, low[8]8入栈栈状态[1, 2, 3, 4, 5, 6, 7, 8]。节点 8 的邻接节点是 77 已在栈中low[8] min(8, 7) 7。节点 8 处理完毕low[8]7不等于 dfn[8]8回溯到 7。节点 7 处理完毕low[7]7等于 dfn[7]7所以 7 是根节点。从栈中弹出直到 7弹出 8、7得到第一个 SCC{7, 8}。栈状态变为[1, 2, 3, 4, 5, 6]。继续回溯到 5节点 5 的所有邻接处理完毕low[5]5等于 dfn[5]5所以 5 是根节点。弹出直到 5弹出 6、5得到第二个 SCC{5, 6}。栈状态变为[1, 2, 3, 4]。这里要注意节点 6 虽然能追溯到节点 4但节点 5 是根节点说明 5 和 6 这个小圈子整体无法逃出到比 5 更早的节点。继续回溯到 4节点 4 处理完毕low[4]4等于 dfn[4]4所以 4 是根节点。弹出直到 4得到第三个 SCC{4}。栈状态变为[1, 2, 3]。继续回溯到 3节点 3 的 low[3]1不等于 dfn[3]3所以 3 不是根节点。回溯到 2low[2] 被子节点 3 的 low 更新为 1low[2]1不等于 dfn[2]2。回溯到 1。节点 1 处理完毕low[1]1等于 dfn[1]1根节点。弹出直到 1得到第四个 SCC{1, 2, 3}。最终得到 4 个强连通分量{7, 8}、{5, 6}、{4}、{1, 2, 3}。注意节点 4、5、6 这一段的归属如果没有 6→4 这条回溯边它们很可能会被拆分得更细但因为这条边存在5 和 6 形成了一个二元 SCC而 4 自己却单独成块这是因为从 5 到 4 的路径被 5 这个根节点切断了。这种情况在真实代码中经常出现亲手模拟一遍就全明白了。3.3 无向图能不能用 Tarjan这里有个大坑顺便提一个很多初学者容易踩的坑Tarjan 算法是为有向图设计的。如果你拿一张无向图去跑 Tarjan试图找“强连通分量”结果会很怪。因为在无向图中如果两个节点之间存在路径那么沿着同一条路径反向也能到达所以无向图的连通分量比 SCC 要宽松得多很多节点会被错误地归并。无向图要用的是另一套基于 Tarjan 衍生出来的算法叫“割点”和“桥”算法。虽然代码形态类似同样用 dfn 和 low 数组但更新 low 的规则完全不一样无向图里遇到已经访问过的、不是父亲的节点直接用它更新 low 值而不是像有向图那样还要额外判断“是否在栈中”。写代码前一定要先确认图是有向还是无向。我见过有人在比赛里把无向图的边存成两个有向边然后套 SCC 模板算出一堆莫名其妙的强连通分量想想都替他觉得亏。4. 完整代码实现与参数选择4.1 基于 C 的 Tarjan 算法标准模板代码实现是检验理解的最好方式。这里给出一份完整的 C 写法代码中加了详细的注释。#include bits/stdc.h using namespace std; const int MAXN 10010; vectorint e[MAXN]; // 邻接表存图 stackint stk; // 算法核心栈 int dfn[MAXN], low[MAXN]; // 时间戳和追溯值 bool inStack[MAXN]; // 标记节点是否在栈中 int timer 0; // 全局时间戳计数器 int sccCnt 0; // 强连通分量计数器 int sccId[MAXN]; // 节点所属的SCC编号缩点用 void tarjan(int u) { dfn[u] low[u] timer; stk.push(u); inStack[u] true; for (int v : e[u]) { if (!dfn[v]) { // 情况1v尚未访问递归搜索 tarjan(v); low[u] min(low[u], low[v]); } else if (inStack[v]) { // 情况2v已访问且在栈中说明有回溯边 low[u] min(low[u], dfn[v]); } // 情况3v已访问但不在栈中属于其他SCC忽略 } // 判断u是否是根节点 if (low[u] dfn[u]) { sccCnt; while (true) { int x stk.top(); stk.pop(); inStack[x] false; sccId[x] sccCnt; if (x u) break; } } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; e[u].push_back(v); // 有向边只加一次 } for (int i 1; i n; i) { if (!dfn[i]) { tarjan(i); // 图可能不连通要逐个检查 } } cout sccCnt endl; return 0; }代码本身不长但是每一行的位置都有讲究。说几个容易写错的细节。第一个细节low[u] 更新时情况 2 用的是 dfn[v] 而不是 low[v]。这是个经典的易错点。原因我之前提过对于回溯边v 已经确定了自己的 dfn直接用它的时间戳来比较即可。如果你写成 low[v]在特定图结构下会出错把本应属于不同 SCC 的节点错误合并。第二个细节dfs 入口的循环处理。很多图不是连通图甚至有孤立节点。主函数里从 1 到 n 逐个检查 dfn 是否为 0是 0 就进入 tarjan。这一步不能省省了就会漏掉某些孤立节点或不连通区域。第三个细节sccId 数组的用途不只是统计数量。在做“缩点”时你需要知道每个节点最终归属于哪个 SCC这个数组就是后续重建图的基础。4.2 Python 实现与递归深度问题的处理Python 版本的代码逻辑完全一致但有一个特别需要注意的地方默认递归深度限制。当图的节点数达到几千甚至上万时Python 的递归深度默认是 1000很容易直接爆栈。所以 Python 代码通常要加下面这样的处理或者干脆用 sys.setrecursionlimit 设置一个大数。import sys sys.setrecursionlimit(10 ** 6) def tarjan(u): global timer, sccCnt timer 1 dfn[u] low[u] timer stack.append(u) in_stack[u] True for v in graph[u]: if dfn[v] 0: tarjan(v) low[u] min(low[u], low[v]) elif in_stack[v]: low[u] min(low[u], dfn[v]) if low[u] dfn[u]: sccCnt 1 while True: x stack.pop() in_stack[x] False scc_id[x] sccCnt if x u: break n, m map(int, input().split()) graph [[] for _ in range(n 1)] for _ in range(m): u, v map(int, input().split()) graph[u].append(v) dfn [0] * (n 1) low [0] * (n 1) in_stack [False] * (n 1) scc_id [0] * (n 1) stack [] timer 0 sccCnt 0 for i in range(1, n 1): if dfn[i] 0: tarjan(i) print(sccCnt)这里有个小技巧如果你面对的图规模很大而且递归很深可以把上面的递归实现改成非递归版本用显式的栈来模拟 DFS。Tarjan 算法本身维护了一个栈再配合系统的递归栈双重栈在某些极端情况下会有性能隐患。不过这种优化在平时做题时不常用一般只有冲刺竞赛、卡常数时才会考虑。对 99% 的场景来说上面的递归写法已经足够稳了。4.3 邻接表、邻接矩阵怎么选图的存储方式对算法效率影响很大特别是当节点数达到十万级时差距会非常明显。邻接矩阵适合节点数少几百以内且需要频繁查询两点之间是否存在边的场景但空间复杂度是 O(n^2)节点一多就爆内存。邻接表适合绝大多数图论算法空间复杂度 O(VE)遍历一个节点的所有邻接边非常自然。Tarjan 算法中每个节点只需要遍历它的所有出边来递归访问邻接表是默认首选。如果你用 Python 写邻接表直接用 list 存 listC 用 vector 数组。都不需要额外引入复杂的数据结构。边权在这个算法中没有任何意义因为我们只关心边的存在性不关心边的长度。5. 常见问题与排查技巧实录5.1 递归爆栈怎么处理这个问题在上面已经提过但值得单独拿出来讲。C 选手在极端数据下也可能会遇到递归栈溢出尤其是节点数达到几十万、图呈链状的时候。常用解法有三个层次第一在代码开头手动扩大系统栈比如 C 里加上 setrlimit但这种方法在比赛环境中未必可用第二把递归写成循环用辅助栈模拟 DFS 过程这样算法栈完全由自己控制不受系统递归深度限制第三调整数据范围策略避开超出常规递归能力的极端场景。非递归版本写起来确实麻烦一些要同时管理访问状态和 low 值更新时机。我给一个简单的思路辅助栈里保存的是 pair(u, 状态)状态为 0 表示首次进入状态为 1 表示子节点处理完毕准备回溯。首次进入时设置 dfn/lf状态为 1 时遍历所有邻接点更新回溯信息并判断是否为根节点。代码量会比递归版本多二三十行但稳定性大大提升。5.2 算出来的 SCC 数量不对三个排查方向如果 Tarjan 运行结果和你手动推演的不一致不要急着怀疑算法先检查下面三个位置。第一检查 low 更新逻辑。情况 2 用的是 dfn[v] 还是 low[v]写成 low[v] 是新手最爱犯的错误表现出的症状是 SCC 数量偏少、节点被错误合并。第二检查主循环是否覆盖了所有节点。图不连通时漏掉了某个节点SCC 数量就会偏少。这个检查起来很简单遍历结束后看看是否所有 dfn 值都非零。第三检查出栈逻辑。正常情况是“弹出直到 u”有人手滑写成了“弹出到栈空为止”直接把整个栈清空结果就全乱了。这种错误的表现是 SCC 数量突然变成 1。还有一个非常隐蔽的坑自环。如果一张图里有节点自己指向自己的边比如 3 → 3Tarjan 算法本身能正确应对因为处理回溯边时会发现在栈中并更新 low 值。但如果你在存图时把自环当成普通边处理可能在读入时出问题。建议在测试数据里加入自环用例确保程序输出正确。5.3 性能优化与大数据量实测经验我拿一张 10 万个节点、20 万条边的随机有向图测过上面这份模板递归版本在 C 中耗时大约 0.2 到 0.5 秒具体看机器和随机图结构。这个性能足以应对绝大多数竞赛和面试场景。但有一种图结构会明显拖慢速度超强连通图也就是几乎任意两个节点都能互相到达的大图。这种图上递归的深度可能达到几万甚至十几万一旦触发栈溢出性能直接就不是毫秒级的问题了。在这种极端情况下我实测过非递归版本的稳定性要远高于递归版本虽然代码量多了一点但换来了万无一失。如果你要参加正式竞赛或者处理大型工程数据强烈建议提前写好一版非递归的模板平时用递归版本调试逻辑提交前切换到非递归版本。另外一个优化小技巧如果确定一张图是稀疏图可以用 vector 的 reserve 预分配空间减少动态扩容带来的不必要开销。节点数很大时这个微优化也能省下几十毫秒。5.4 缩点之后怎么用一个真实案例Tarjan 算法最常见的后续操作是“缩点”把每一个 SCC 看作一个超级节点原图中的边按照 SCC 之间的连接关系重建。缩点之后整张图一定是一个 DAG有向无环图。这个性质非常有用因为 DAG 上可以做拓扑排序、动态规划等更复杂的操作。给你一个经典应用场景某系统里有一堆任务任务之间通过有向依赖关系连接。如果存在循环依赖这些任务就没法确定执行顺序。用 Tarjan 算法找出所有 SCC如果某个 SCC 中包含的节点数大于 1说明这个子集存在循环依赖需要单独处理。把每个 SCC 缩成一个点之后就可以对 DAG 做拓扑排序得到一个合理的执行顺序。另外求“从某个节点出发能否到达所有节点”这类问题第一步通常也是先求 SCC 再缩点。因为强连通分量内部任意两个节点互相可达可以看作一个整体。缩完点后DAG 上的问题往往比原图简单得多。我之前处理过一个实际的爬虫去重需求把上万个 URL 看成节点URL 之间的跳转关系看成有向边用 Tarjan 找出所有互相可达的 URL 集合把它们合并为一个站点组后续去重和抓取策略都基于这个分组来做效率比单纯按域名分组高很多。这个例子可能不算特别典型但能说明 SCC 的适用范围远不止竞赛题。6. 最后分享一点个人体会Tarjan 算法是我学过的图论算法里少有的“代码极短但思维量极大”的类型。它只用两个数组加一个栈就能在一次 DFS 内解决强连通分量问题这种精巧程度是其他算法少见的。每次手动推演一张图的完整过程都会有新的体会。学这个算法最忌讳的就是只看代码不动手。我的建议是找一张十几条边的有向图自己画在纸上从头到尾模拟完整过程记录每一步栈的状态和数组变化。等你模拟出两三个 SCC 之后再看代码会觉得每个变量的用途都通透无比。这比任何讲解都有效。如果这篇文章对你有点帮助顺手自己写一版代码跑几个测试用例比收藏起来吃灰有用一万倍。强连通分量的思路培养起来之后你再去看缩点、2-SAT 这些问题会发现它们都建立在同一套核心思想上一通百通。 
长河君 · 2026/10/10 21:28:36 · 阅读 1.2k Tarjan算法详解：一次DFS找出所有强连通分量
1. 写在最前面这玩意儿到底是干嘛的强连通分量英文全称 Strongly Connected Components圈内习惯简写为 SCC。第一次接触图论算法的人看到这个概念脑子里大概率是一团浆糊什么叫“强连通”跟“连通”又差在哪儿最直观的理解方式是这样的。想象一个有向图里的若干节点是一伙人强连通分量就是这样一个“小圈子”圈子里的任何一个人都能沿着有向边找到路走到圈子里的任何一个其他人。注意是有向边这就和普通的无向图连通性彻底拉开了差距。无向图里你只要有一条路能走反过来也能走有向图里你从 A 能到 B并不代表 B 能回到 A。所以强连通分量专门处理的是“互相可达”这种更强的关系。Tarjan 算法就是用来在一张有向图里把所有这些“小圈子”一个不落地找出来的经典算法。它由 Robert Tarjan 在 1972 年提出来用一次深度优先搜索DFS就能搞定时间复杂度 O(VE)空间复杂度也基本是 O(V)。这个效率在同类算法里属于顶级水平和他同时期的 Kosaraju 算法相比省去了“对原图做一遍 DFS、对反图再做一遍 DFS”的两轮遍历而是只靠一套 DFS 流程就同时完成了“发现”和“归类”两个动作。在这个领域里Tarjan 算法几乎是面试和竞赛的必备考点。你在处理“缩点”“2-SAT”“最小环”“必经点”等问题的时候第一步往往就是找 SCC。可以把它理解成高级图论问题的一块地基地基没打牢上面的建筑全白搭。这篇文章就来完整拆解一下这个算法的原理、实现、常见问题和调试技巧全是实操积累的东西。你要是能耐心看到最后一个章节遇到相关题目基本能直接上手写代码。2. 整体设计思路拆解为什么 Tarjan 能一趟 DFS 解决问题2.1 从“搜索树”到“回溯边”的观察初次接触 Tarjan 算法最让人困惑的点是它到底凭什么在一次 DFS 中就能把所有 SCC 找出来核心逻辑藏在 DFS 的过程里。你对一张有向图做深度优先遍历会自然生成一棵“DFS 搜索树”树上的边是实际递归走过的边。但原图里还有一些边是搜索树中没有走过的它们指向已经访问过的节点这些边就是“回溯边”也叫返祖边。强连通分量之所以能形成靠的正是这些回溯边把搜索树上的几条路径“连接”起来形成闭环。举个例子假设从节点 1 开始搜索走到节点 2走到节点 3结果节点 3 有一条边指向节点 1。这样一来节点 1、2、3 就构成了一个环也就是一个完整的 SCC。Tarjan 算法的聪明之处在于它用两个时间戳数组记录 DFS 过程中的关键信息然后根据这些信息判断一个节点能否成为某个 SCC 的“根”。这里强烈建议你拿纸笔手动模拟一遍随便画一张有 7 个节点的有向图按自己的习惯编号然后人工执行一遍 DFS记录每个节点的访问顺序和栈的变化。我当年学这个算法的时候就是靠这样画了五六张图才彻底把逻辑理清楚。只看代码是学不会 Tarjan 的必须亲手模拟。2.2 两个核心数组dfn 和 lowTarjan 算法离不开两个数组分别是 dfn 和 low。dfn[u] 表示节点 u 在 DFS 过程中被首次访问的时间戳也就是访问顺序编号这个编号一旦确定就不会再改变。low[u] 表示节点 u 通过自身的子树内节点和至多一条回溯边能够追溯到的“最早”时间戳。也就是说low[u] 的维护目标是最小化“能到达的、还在栈中的节点”的 dfn 值。这里最重要的限制是“还在栈中”——因为栈里保存的是当前尚未处理完的、可能属于同一个 SCC 的节点集合。如果目标节点已经出栈了说明它已经属于另一个 SCC 了不能再去更新 low 值。每次 DFS 到一个新节点 u先把 dfn[u] 和 low[u] 都初始化为当前时间戳加一然后把 u 压入栈中继续递归访问它的所有邻接节点 v。递归返回后用 low[v] 去更新 low[u]。这里要特别注意区分三种情况对应三种不同的处理方式。第一种情况v 尚未被访问过dfn[v] 为 0这意味着 v 是从 u 出发在搜索树上的子节点那么递归访问 v然后 low[u] min(low[u], low[v])。第二种情况v 已经被访问过而且还在栈中说明 v 是 u 的“祖先”或者“祖先的后代路径上某个尚未处理的节点”此时用 dfn[v] 更新 low[u]low[u] min(low[u], dfn[v])。这里用的不是 low[v]而是 dfn[v]因为这个更新动作针对的是回溯边回溯边的终点是当前搜索树上已经确定编号的节点用 dfn 值来比较最合适。第三种情况v 已经被访问过但已经不在栈中说明 v 属于一个已经确定完成的 SCC这条边对于当前 u 的 low 值没有任何意义直接忽略。2.3 判断根节点的条件与“出栈”操作在 u 的所有邻接节点访问完毕之后如果发现 low[u] 等于 dfn[u]那 u 就是当前这个强连通分量的“根”。为什么因为 low[u] 等于 dfn[u] 意味着什么意味着 u 无法通过子树中的任何节点、任何回溯边追溯到比 u 更早访问的节点。换句话说u 是整个这个小圈子里的“最早祖先”这个圈子的所有节点都在 u 的子树里。这时候就把栈中的节点依次弹出直到弹出 u 为止。所有弹出的节点构成一个完整的 SCC。这里有一个很关键的小细节弹出的过程中你可能先弹出的是后来入栈的节点这些节点的 dfn 值一定大于 u 的 dfn 值它们也就是 u 的子树中的节点。弹到 u 为止说明这条“链”上的所有节点都能互相到达。有人可能会问为什么 low[u] 等于 dfn[u] 就一定意味着 u 是根而不是某个子树节点正好把 low 值同化成 dfn[u]仔细想一下 low 的更新规则就能理解子树里的节点想把 low 值变小必须依赖一条能走到更早节点的路径而要走到比 u 更早的节点必然意味着有一条边从 u 的子树指向 u 的祖先——这种情况下 low[u] 早就在回溯边处理时被更新成更小的值了。所以当 low[u] 保持等于 dfn[u] 的状态就说明它的子树完全“封闭”了再没有任何路径可以逃出这个圈子。3. 核心细节解析与实操要点3.1 为什么栈是算法的灵魂Tarjan 算法的另一大支柱就是那个显式的栈。这个栈的灵魂在于它维护的是“当前还在被处理中的搜索路径上尚未归属任何 SCC 的节点集合”。这个栈和普通 DFS 的系统递归栈有什么区别系统递归栈只记录函数调用链而 Tarjan 的栈记录的是“按访问顺序加入、尚未确定归属”的节点。当一个 SCC 被确定后它的所有节点会一股脑儿弹出去从栈中整体消失。这就意味着栈中任意两个相邻节点之间未必有直接的边连接但它们在访问顺序上是连续的而且它们都在等待被归类到某个 SCC 中。理解这个栈的关键场景是遇到回溯边把 low 值更新到更早的节点。比如节点 6 有一条回溯边指向节点 2那么节点 6 的 low 值会被更新为 dfn[2] 的值。这个值可能比某个中间节点的 low 值小很多从而在后续判断根节点时产生连锁反应。若没有栈来标记哪些节点还在处理中你就没办法区分“一条边指向仍在等待归类的节点”和“一条边指向已经归类完毕的节点”算法逻辑就会出现严重错误。我见过不少人在自己实现 Tarjan 的时候省掉了栈或者用 visited 数组替代结果算出来的 SCC 数量总是偏多。原因就在这儿去了栈就丢了“时间顺序”等于把算法最重要的状态给扔了。3.2 动手模拟一张 8 节点图的完整过程理论讲得再多不如手动推演一遍。下面这张图包含 8 个节点边按以下规则建立1 → 22 → 33 → 13 → 44 → 55 → 66 → 45 → 77 → 88 → 7从节点 1 开始执行 Tarjan 算法。访问 1dfn[1]1, low[1]1入栈栈状态[1]。从 1 走到 2dfn[2]2, low[2]2入栈栈状态[1, 2]。从 2 走到 3dfn[3]3, low[3]3入栈栈状态[1, 2, 3]。节点 3 的邻接节点是 1 和 4。先处理 11 已经在栈中所以 low[3] min(low[3], dfn[1]) min(3, 1) 1。这表示节点 3 可以通过回溯边 3→1 追溯到最早访问的节点 1。接着处理 4dfn[4]4, low[4]4入栈栈状态[1, 2, 3, 4]。从 4 走到 5dfn[5]5, low[5]5入栈栈状态[1, 2, 3, 4, 5]。从 5 走到 6dfn[6]6, low[6]6入栈栈状态[1, 2, 3, 4, 5, 6]。节点 6 的邻接节点是 44 已经在栈中所以 low[6] min(low[6], dfn[4]) min(6, 4) 4。节点 6 处理完毕low[6]4不等于 dfn[6]6所以 6 不是根节点继续回溯到 5。节点 5 的另一个邻接节点是 7。访问 7dfn[7]7, low[7]7入栈栈状态[1, 2, 3, 4, 5, 6, 7]。从 7 走到 8dfn[8]8, low[8]8入栈栈状态[1, 2, 3, 4, 5, 6, 7, 8]。节点 8 的邻接节点是 77 已在栈中low[8] min(8, 7) 7。节点 8 处理完毕low[8]7不等于 dfn[8]8回溯到 7。节点 7 处理完毕low[7]7等于 dfn[7]7所以 7 是根节点。从栈中弹出直到 7弹出 8、7得到第一个 SCC{7, 8}。栈状态变为[1, 2, 3, 4, 5, 6]。继续回溯到 5节点 5 的所有邻接处理完毕low[5]5等于 dfn[5]5所以 5 是根节点。弹出直到 5弹出 6、5得到第二个 SCC{5, 6}。栈状态变为[1, 2, 3, 4]。这里要注意节点 6 虽然能追溯到节点 4但节点 5 是根节点说明 5 和 6 这个小圈子整体无法逃出到比 5 更早的节点。继续回溯到 4节点 4 处理完毕low[4]4等于 dfn[4]4所以 4 是根节点。弹出直到 4得到第三个 SCC{4}。栈状态变为[1, 2, 3]。继续回溯到 3节点 3 的 low[3]1不等于 dfn[3]3所以 3 不是根节点。回溯到 2low[2] 被子节点 3 的 low 更新为 1low[2]1不等于 dfn[2]2。回溯到 1。节点 1 处理完毕low[1]1等于 dfn[1]1根节点。弹出直到 1得到第四个 SCC{1, 2, 3}。最终得到 4 个强连通分量{7, 8}、{5, 6}、{4}、{1, 2, 3}。注意节点 4、5、6 这一段的归属如果没有 6→4 这条回溯边它们很可能会被拆分得更细但因为这条边存在5 和 6 形成了一个二元 SCC而 4 自己却单独成块这是因为从 5 到 4 的路径被 5 这个根节点切断了。这种情况在真实代码中经常出现亲手模拟一遍就全明白了。3.3 无向图能不能用 Tarjan这里有个大坑顺便提一个很多初学者容易踩的坑Tarjan 算法是为有向图设计的。如果你拿一张无向图去跑 Tarjan试图找“强连通分量”结果会很怪。因为在无向图中如果两个节点之间存在路径那么沿着同一条路径反向也能到达所以无向图的连通分量比 SCC 要宽松得多很多节点会被错误地归并。无向图要用的是另一套基于 Tarjan 衍生出来的算法叫“割点”和“桥”算法。虽然代码形态类似同样用 dfn 和 low 数组但更新 low 的规则完全不一样无向图里遇到已经访问过的、不是父亲的节点直接用它更新 low 值而不是像有向图那样还要额外判断“是否在栈中”。写代码前一定要先确认图是有向还是无向。我见过有人在比赛里把无向图的边存成两个有向边然后套 SCC 模板算出一堆莫名其妙的强连通分量想想都替他觉得亏。4. 完整代码实现与参数选择4.1 基于 C 的 Tarjan 算法标准模板代码实现是检验理解的最好方式。这里给出一份完整的 C 写法代码中加了详细的注释。#include bits/stdc.h using namespace std; const int MAXN 10010; vectorint e[MAXN]; // 邻接表存图 stackint stk; // 算法核心栈 int dfn[MAXN], low[MAXN]; // 时间戳和追溯值 bool inStack[MAXN]; // 标记节点是否在栈中 int timer 0; // 全局时间戳计数器 int sccCnt 0; // 强连通分量计数器 int sccId[MAXN]; // 节点所属的SCC编号缩点用 void tarjan(int u) { dfn[u] low[u] timer; stk.push(u); inStack[u] true; for (int v : e[u]) { if (!dfn[v]) { // 情况1v尚未访问递归搜索 tarjan(v); low[u] min(low[u], low[v]); } else if (inStack[v]) { // 情况2v已访问且在栈中说明有回溯边 low[u] min(low[u], dfn[v]); } // 情况3v已访问但不在栈中属于其他SCC忽略 } // 判断u是否是根节点 if (low[u] dfn[u]) { sccCnt; while (true) { int x stk.top(); stk.pop(); inStack[x] false; sccId[x] sccCnt; if (x u) break; } } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; e[u].push_back(v); // 有向边只加一次 } for (int i 1; i n; i) { if (!dfn[i]) { tarjan(i); // 图可能不连通要逐个检查 } } cout sccCnt endl; return 0; }代码本身不长但是每一行的位置都有讲究。说几个容易写错的细节。第一个细节low[u] 更新时情况 2 用的是 dfn[v] 而不是 low[v]。这是个经典的易错点。原因我之前提过对于回溯边v 已经确定了自己的 dfn直接用它的时间戳来比较即可。如果你写成 low[v]在特定图结构下会出错把本应属于不同 SCC 的节点错误合并。第二个细节dfs 入口的循环处理。很多图不是连通图甚至有孤立节点。主函数里从 1 到 n 逐个检查 dfn 是否为 0是 0 就进入 tarjan。这一步不能省省了就会漏掉某些孤立节点或不连通区域。第三个细节sccId 数组的用途不只是统计数量。在做“缩点”时你需要知道每个节点最终归属于哪个 SCC这个数组就是后续重建图的基础。4.2 Python 实现与递归深度问题的处理Python 版本的代码逻辑完全一致但有一个特别需要注意的地方默认递归深度限制。当图的节点数达到几千甚至上万时Python 的递归深度默认是 1000很容易直接爆栈。所以 Python 代码通常要加下面这样的处理或者干脆用 sys.setrecursionlimit 设置一个大数。import sys sys.setrecursionlimit(10 ** 6) def tarjan(u): global timer, sccCnt timer 1 dfn[u] low[u] timer stack.append(u) in_stack[u] True for v in graph[u]: if dfn[v] 0: tarjan(v) low[u] min(low[u], low[v]) elif in_stack[v]: low[u] min(low[u], dfn[v]) if low[u] dfn[u]: sccCnt 1 while True: x stack.pop() in_stack[x] False scc_id[x] sccCnt if x u: break n, m map(int, input().split()) graph [[] for _ in range(n 1)] for _ in range(m): u, v map(int, input().split()) graph[u].append(v) dfn [0] * (n 1) low [0] * (n 1) in_stack [False] * (n 1) scc_id [0] * (n 1) stack [] timer 0 sccCnt 0 for i in range(1, n 1): if dfn[i] 0: tarjan(i) print(sccCnt)这里有个小技巧如果你面对的图规模很大而且递归很深可以把上面的递归实现改成非递归版本用显式的栈来模拟 DFS。Tarjan 算法本身维护了一个栈再配合系统的递归栈双重栈在某些极端情况下会有性能隐患。不过这种优化在平时做题时不常用一般只有冲刺竞赛、卡常数时才会考虑。对 99% 的场景来说上面的递归写法已经足够稳了。4.3 邻接表、邻接矩阵怎么选图的存储方式对算法效率影响很大特别是当节点数达到十万级时差距会非常明显。邻接矩阵适合节点数少几百以内且需要频繁查询两点之间是否存在边的场景但空间复杂度是 O(n^2)节点一多就爆内存。邻接表适合绝大多数图论算法空间复杂度 O(VE)遍历一个节点的所有邻接边非常自然。Tarjan 算法中每个节点只需要遍历它的所有出边来递归访问邻接表是默认首选。如果你用 Python 写邻接表直接用 list 存 listC 用 vector 数组。都不需要额外引入复杂的数据结构。边权在这个算法中没有任何意义因为我们只关心边的存在性不关心边的长度。5. 常见问题与排查技巧实录5.1 递归爆栈怎么处理这个问题在上面已经提过但值得单独拿出来讲。C 选手在极端数据下也可能会遇到递归栈溢出尤其是节点数达到几十万、图呈链状的时候。常用解法有三个层次第一在代码开头手动扩大系统栈比如 C 里加上 setrlimit但这种方法在比赛环境中未必可用第二把递归写成循环用辅助栈模拟 DFS 过程这样算法栈完全由自己控制不受系统递归深度限制第三调整数据范围策略避开超出常规递归能力的极端场景。非递归版本写起来确实麻烦一些要同时管理访问状态和 low 值更新时机。我给一个简单的思路辅助栈里保存的是 pair(u, 状态)状态为 0 表示首次进入状态为 1 表示子节点处理完毕准备回溯。首次进入时设置 dfn/lf状态为 1 时遍历所有邻接点更新回溯信息并判断是否为根节点。代码量会比递归版本多二三十行但稳定性大大提升。5.2 算出来的 SCC 数量不对三个排查方向如果 Tarjan 运行结果和你手动推演的不一致不要急着怀疑算法先检查下面三个位置。第一检查 low 更新逻辑。情况 2 用的是 dfn[v] 还是 low[v]写成 low[v] 是新手最爱犯的错误表现出的症状是 SCC 数量偏少、节点被错误合并。第二检查主循环是否覆盖了所有节点。图不连通时漏掉了某个节点SCC 数量就会偏少。这个检查起来很简单遍历结束后看看是否所有 dfn 值都非零。第三检查出栈逻辑。正常情况是“弹出直到 u”有人手滑写成了“弹出到栈空为止”直接把整个栈清空结果就全乱了。这种错误的表现是 SCC 数量突然变成 1。还有一个非常隐蔽的坑自环。如果一张图里有节点自己指向自己的边比如 3 → 3Tarjan 算法本身能正确应对因为处理回溯边时会发现在栈中并更新 low 值。但如果你在存图时把自环当成普通边处理可能在读入时出问题。建议在测试数据里加入自环用例确保程序输出正确。5.3 性能优化与大数据量实测经验我拿一张 10 万个节点、20 万条边的随机有向图测过上面这份模板递归版本在 C 中耗时大约 0.2 到 0.5 秒具体看机器和随机图结构。这个性能足以应对绝大多数竞赛和面试场景。但有一种图结构会明显拖慢速度超强连通图也就是几乎任意两个节点都能互相到达的大图。这种图上递归的深度可能达到几万甚至十几万一旦触发栈溢出性能直接就不是毫秒级的问题了。在这种极端情况下我实测过非递归版本的稳定性要远高于递归版本虽然代码量多了一点但换来了万无一失。如果你要参加正式竞赛或者处理大型工程数据强烈建议提前写好一版非递归的模板平时用递归版本调试逻辑提交前切换到非递归版本。另外一个优化小技巧如果确定一张图是稀疏图可以用 vector 的 reserve 预分配空间减少动态扩容带来的不必要开销。节点数很大时这个微优化也能省下几十毫秒。5.4 缩点之后怎么用一个真实案例Tarjan 算法最常见的后续操作是“缩点”把每一个 SCC 看作一个超级节点原图中的边按照 SCC 之间的连接关系重建。缩点之后整张图一定是一个 DAG有向无环图。这个性质非常有用因为 DAG 上可以做拓扑排序、动态规划等更复杂的操作。给你一个经典应用场景某系统里有一堆任务任务之间通过有向依赖关系连接。如果存在循环依赖这些任务就没法确定执行顺序。用 Tarjan 算法找出所有 SCC如果某个 SCC 中包含的节点数大于 1说明这个子集存在循环依赖需要单独处理。把每个 SCC 缩成一个点之后就可以对 DAG 做拓扑排序得到一个合理的执行顺序。另外求“从某个节点出发能否到达所有节点”这类问题第一步通常也是先求 SCC 再缩点。因为强连通分量内部任意两个节点互相可达可以看作一个整体。缩完点后DAG 上的问题往往比原图简单得多。我之前处理过一个实际的爬虫去重需求把上万个 URL 看成节点URL 之间的跳转关系看成有向边用 Tarjan 找出所有互相可达的 URL 集合把它们合并为一个站点组后续去重和抓取策略都基于这个分组来做效率比单纯按域名分组高很多。这个例子可能不算特别典型但能说明 SCC 的适用范围远不止竞赛题。6. 最后分享一点个人体会Tarjan 算法是我学过的图论算法里少有的“代码极短但思维量极大”的类型。它只用两个数组加一个栈就能在一次 DFS 内解决强连通分量问题这种精巧程度是其他算法少见的。每次手动推演一张图的完整过程都会有新的体会。学这个算法最忌讳的就是只看代码不动手。我的建议是找一张十几条边的有向图自己画在纸上从头到尾模拟完整过程记录每一步栈的状态和数组变化。等你模拟出两三个 SCC 之后再看代码会觉得每个变量的用途都通透无比。这比任何讲解都有效。如果这篇文章对你有点帮助顺手自己写一版代码跑几个测试用例比收藏起来吃灰有用一万倍。强连通分量的思路培养起来之后你再去看缩点、2-SAT 这些问题会发现它们都建立在同一套核心思想上一通百通。