企业官网建设流程全解析

1. 写在最前面：这玩意儿到底是干嘛的

强连通分量，英文全称 Strongly Connected Components，圈内习惯简写为 SCC。第一次接触图论算法的人看到这个概念，脑子里大概率是一团浆糊：什么叫“强连通”？跟“连通”又差在哪儿？

最直观的理解方式是这样的。想象一个有向图里的若干节点是一伙人，强连通分量就是这样一个“小圈子”：圈子里的任何一个人，都能沿着有向边找到路走到圈子里的任何一个其他人。注意，是有向边，这就和普通的无向图连通性彻底拉开了差距。无向图里你只要有一条路能走，反过来也能走；有向图里你从 A 能到 B，并不代表 B 能回到 A。所以强连通分量专门处理的，是“互相可达”这种更强的关系。

Tarjan 算法就是用来在一张有向图里，把所有这些“小圈子”一个不落地找出来的经典算法。它由 Robert Tarjan 在 1972 年提出来，用一次深度优先搜索（DFS）就能搞定，时间复杂度 O(V+E)，空间复杂度也基本是 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 和 low

Tarjan 算法离不开两个数组，分别是 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 → 2
• 2 → 3
• 3 → 1
• 3 → 4
• 4 → 5
• 5 → 6
• 6 → 4
• 5 → 7
• 7 → 8
• 8 → 7

从节点 1 开始执行 Tarjan 算法。

访问 1，dfn[1]=1, low[1]=1，入栈，栈状态：[1]。

从 1 走到 2，dfn[2]=2, low[2]=2，入栈，栈状态：[1, 2]。

从 2 走到 3，dfn[3]=3, low[3]=3，入栈，栈状态：[1, 2, 3]。

节点 3 的邻接节点是 1 和 4。先处理 1：1 已经在栈中，所以 low[3] = min(low[3], dfn[1]) = min(3, 1) = 1。这表示节点 3 可以通过回溯边 3→1 追溯到最早访问的节点 1。

接着处理 4：dfn[4]=4, low[4]=4，入栈，栈状态：[1, 2, 3, 4]。

从 4 走到 5，dfn[5]=5, low[5]=5，入栈，栈状态：[1, 2, 3, 4, 5]。

从 5 走到 6，dfn[6]=6, low[6]=6，入栈，栈状态：[1, 2, 3, 4, 5, 6]。

节点 6 的邻接节点是 4，4 已经在栈中，所以 low[6] = min(low[6], dfn[4]) = min(6, 4) = 4。

节点 6 处理完毕，low[6]=4，不等于 dfn[6]=6，所以 6 不是根节点，继续回溯到 5。

节点 5 的另一个邻接节点是 7。访问 7，dfn[7]=7, low[7]=7，入栈，栈状态：[1, 2, 3, 4, 5, 6, 7]。

从 7 走到 8，dfn[8]=8, low[8]=8，入栈，栈状态：[1, 2, 3, 4, 5, 6, 7, 8]。

节点 8 的邻接节点是 7，7 已在栈中，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 不是根节点。回溯到 2，low[2] 被子节点 3 的 low 更新为 1，low[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; vector<int> e[MAXN]; // 邻接表存图 stack<int> 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]) { // 情况1：v尚未访问，递归搜索 tarjan(v); low[u] = min(low[u], low[v]); } else if (inStack[v]) { // 情况2：v已访问且在栈中，说明有回溯边 low[u] = min(low[u], dfn[v]); } // 情况3：v已访问但不在栈中，属于其他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(V+E)，遍历一个节点的所有邻接边非常自然。Tarjan 算法中，每个节点只需要遍历它的所有出边来递归访问，邻接表是默认首选。

如果你用 Python 写邻接表，直接用 list 存 list；C++ 用 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 → 3，Tarjan 算法本身能正确应对，因为处理回溯边时会发现在栈中并更新 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 这些问题，会发现它们都建立在同一套核心思想上，一通百通。