企业官网建设流程全解析

很多搞过竞赛或者刷过题的朋友，应该都听过 Tarjan 算法的大名。第一次接触的时候，看着那段短短的递归代码，配上 dfn、low、栈这三个东西，不少人是懵的：为什么这样就能找出一堆互相可达的点？为什么代码那么短却看起来那么难懂？我当年也是啃了很久，踩了不少坑，才终于把它的运行过程在脑子里跑通。这篇文章我把自己的理解完整捋一遍，不光是强连通分量，还会把桥、割点、离线 LCA 这些同源扩展一并聊清楚，希望能帮你真正把 Tarjan 算法装进脑子里，而不是只会背代码。

Tarjan 算法本质上是一套基于深度优先搜索的图连通性分析工具，最经典、最核心的用途是求有向图的强连通分量。学懂它意味着你会用 O(N+M) 的时间复杂度拿到图中所有“环上互相可达”的点集，这对解决有向图中的判环、缩点、依赖分析、条件环检测等问题都是致命武器。适合正在学图论算法、准备面试或者竞赛、以及需要处理复杂依赖关系的数据工程师、底层技术人员参考。

1. 从问题说起：为什么需要找“强连通分量”

1.1 强连通分量是什么

先看一个最朴素的定义：在一个有向图里，如果从顶点 A 能到达顶点 B，同时从顶点 B 也能到达顶点 A，我们就说 A 和 B 是强连通的。把图中所有互相强连通的点放在一起，形成的极大点集，就叫强连通分量，简称 SCC。

理解“极大”很关键。举个例子：三个点 A、B、C，有边 A->B、B->A、B->C、C->B。那么 A 和 B 互相可达，B 和 C 互相可达，因此 A、B、C 三个点任意两点都互相可达吗？从 A 能否到 C？A->B->C，能。从 C 能否到 A？C->B->A，能。所以三个点整体构成一个强连通分量。这个集合是“极大”的，因为再加入任何一个其他点都无法保持两两可达的性质。如果存在一个点只跟这个分量里的部分点连通，它不会属于当前这个分量。

强连通分量和有向图中的“环”直接相关。任何一个长度大于 1 的环上所有点都在同一个 SCC 里，多个环共用交点时，交缠在一起的整个连通块也是一个 SCC。所以找 SCC 本质上就是在有向图中找环，而 Tarjan 算法就是最高效的那一种。

1.2 强连通分量的应用场景

场景一：判环与死锁检测。数据库事务依赖、任务调度 DAG 中如果有环，往往意味着死锁或者循环依赖。Tarjan 缩点后检查是否存在大小为 1 以上或者多条边的 SCC，就能快速定位问题。

场景二：缩点化简图结构。把一个 SCC 缩成一个“超级节点”后，有向图就变成一个 DAG。DAG 可以做拓扑排序、最长路径、状态压缩 DP，复杂度通常远低于原来带环的图。比如在编译器中分析模块之间的依赖关系，把强连通模块合并，再决定编译顺序，就是这个思路的工程化落地。

场景三：2-SAT 判定。2-SAT 问题需要判断一组布尔表达式是否存在赋值使其成立，经典做法就是把每个变量的真和假拆成两个点建图，然后跑 Tarjan 判 SCC。如果某个变量的两个状态在同一个 SCC 里，说明无解。这个应用在竞赛题和真实约束求解里都很常见。

场景四：闭包传递与等价类。社交网络中互相关注的用户集群、软件逆向里函数调用关系形成的递归环，都可以用 SCC 来抽取等价类，做聚类或者模块化分析。

2. Tarjan算法的核心思路与两个关键数组

2.1 深度优先搜索与时间戳

Tarjan 算法的一切都建立在深度优先搜索之上。从某个起点开始，一路沿着边往下走，直到走不动再回溯。在 DFS 的过程中，给每个第一次访问到的节点打上一个递增的编号，这个编号就是 dfn，也就是“发现时间戳”。因为 DFS 访问节点的顺序是唯一的，所以每个节点的 dfn 也是唯一的、递增的。

时间戳本身并不神奇，神奇的是如何利用它来判断连通关系。想象一下，如果两个点强连通，那么 DFS 从其中一个点开始搜索时，一定能在回到这个点之前途经另一个点。反之，如果从一个点出去的所有路径都无法回到它自己，那它就不可能和其他点形成强连通分量。Tarjan 算法正是用一个额外的 low 值来记录“这个点通过自己的子孙能回溯到的最早时间戳”。

2.2 dfn与low的含义

dfn[v] 表示顶点 v 被 DFS 访问到的顺序编号。low[v] 表示在 DFS 树中，从 v 出发，通过 v 的子树以及最多一条“回边”（也就是指向祖先的边）能够到达的节点的最小 dfn 值。这个定义写得很绕，但理解它只需要抓住一句话：low[v] 是 v 所在的强连通分量中，最早被访问的那个节点的 dfn。

为什么 low 可以指示强连通分量？因为一个强连通分量内部必然存在至少一个“根”，这个根是分量中 dfn 最小的节点。当 DFS 从根进入分量后，会沿着某些路径走遍分量内所有节点，最后通过回边回到根，于是所有节点的 low 都会被更新到根的时间戳附近。当 DFS 回溯到根时，发现 low[root] == dfn[root]，就说明以 root 为根的这棵子树里，再往上找不到能回到更早祖先的回边了，于是当前栈顶到 root 之间所有节点就形成一个完整的 SCC。

2.3 栈的作用

Tarjan 需要一个栈来保存“当前尚未确定归属的节点”。规则是：每次 DFS 到一个新节点，就将其入栈。当发现一个节点的 low[root] == dfn[root] 时，从栈顶一直弹出到 root 为止，这些弹出的节点就是一个强连通分量。

为什么必须用栈？因为 DFS 是基于栈的递归过程，而强连通分量的“根”发现时，该分量里的所有节点一定还在栈中且紧挨着。如果一个节点已经被弹出了，说明它已经属于之前某个已确定的分量，不可能再和后续节点形成新的分量。栈的存在保证了我们只对“当前仍有资格形成分量”的节点进行截取。

打个不恰当的比方：栈就像一张拼图工作台，一边拼、一边把不确定的碎片放上去，一旦某个局部图案完整了，就整体收走放在成品区。剩下的碎片继续拼，永远不会混到已经收走的图块里。

3. 手撕Tarjan：完整步骤与代码实现

3.1 算法流程拆解

我把 Tarjan 求强连通分量的完整流程拆成下面几步：

1. 从任意未访问节点出发，执行 DFS。每个节点首次进入时，初始化 dfn[v] = low[v] = 时间戳计数器，并将 v 入栈。
2. 遍历 v 的所有邻接点 u：
   • 如果 u 尚未访问，就递归 DFS(u)，回来后用 low[u] 更新 low[v]，即 low[v] = min(low[v], low[u])。
   • 如果 u 已经被访问过，且 u 还在栈中，说明发现了一条回边或者横叉边，此时用 dfn[u] 更新 low[v]，即 low[v] = min(low[v], dfn[u])。注意这里用的是 dfn[u] 而非 low[u]，这是很多初学者最容易写错的地方。
3. 递归返回后，检查 low[v] 是否等于 dfn[v]。如果相等，说明 v 是某个强连通分量的根，于是不断从栈顶弹出节点，直到弹出 v 为止，这些节点构成一个 SCC。
4. 继续遍历其他未访问节点，直到所有节点都被处理。

步骤 2 中的两个分支是核心。第一个分支处理的是“树边”：子节点通过递归已经算出它至少能回溯到哪个祖先，父节点自然要继承这个信息。第二个分支处理的是“非树边”：u 已经被访问且还在栈中，说明 u 是 v 的祖先（或者祖先的某个旁系，但重要的是 u 在当前根到 v 的路径上），所以 v 能回到的时间戳至少是 dfn[u]，取 min 即可。如果 u 不在栈中，说明它已经属于某个已经完结的分量，它和 v 之间的边不能帮助 v 往上回溯，必须忽略。

3.2 核心代码（C++示例）

#include <bits/stdc++.h> using namespace std; const int MAXN = 10005; vector<int> g[MAXN]; int dfn[MAXN], low[MAXN], scc_id[MAXN]; int timer = 0, scc_cnt = 0; stack<int> st; bool in_stack[MAXN]; void tarjan(int v) { dfn[v] = low[v] = ++timer; st.push(v); in_stack[v] = true; for (int u : g[v]) { if (!dfn[u]) { tarjan(u); low[v] = min(low[v], low[u]); } else if (in_stack[u]) { low[v] = min(low[v], dfn[u]); } } if (low[v] == dfn[v]) { ++scc_cnt; int x; do { x = st.top(); st.pop(); in_stack[x] = false; scc_id[x] = scc_cnt; } while (x != v); } } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; g[a].push_back(b); } for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); } cout << "SCC 数量: " << scc_cnt << endl; for (int i = 1; i <= scc_cnt; i++) { cout << "SCC " << i << ": "; for (int v = 1; v <= n; v++) { if (scc_id[v] == i) cout << v << " "; } cout << endl; } return 0; }

这段代码很短，但值得逐行解释。外层循环保证了对非连通图中每个连通块都做一次 DFS。递归函数里，if (!dfn[u])判断 u 是否未访问过，如果没访问过就深入递归，回传后更新 low；else if (in_stack[u])处理回边，用 dfn[u] 更新。注意 low[v] 的初始化就是 dfn[v] 本身，相等时说明这条路径上最多只能回溯到自己，于是自己就是分量根。

3.3 图解一个小例子

我们用一个简单图来模拟：5 个节点，边如下：1->2, 2->3, 3->1, 3->4, 4->5, 5->4。

从 1 开始 DFS：

• 1: dfn=1, low=1，入栈。
• 1->2: 2 未访问，递归到 2，dfn=2, low=2，入栈。
• 2->3: 3 未访问，递归到 3，dfn=3, low=3，入栈。
• 3->1: 1 已访问且在栈中，low[3] = min(3, dfn[1]=1) = 1。
• 3->4: 4 未访问，递归到 4，dfn=4, low=4，入栈。
• 4->5: 5 未访问，递归到 5，dfn=5, low=5，入栈。
• 5->4: 4 已访问且在栈中，low[5] = min(5, 4) = 4。
• 5 的邻接遍历完，low[5]=4 != dfn[5]=5，不弹出。返回 4。
• 4 的邻接只剩一个，接收 low[5]=4，low[4] = min(4,4)=4。low[4]=4 != dfn[4]=4？相等！所以弹出栈顶到 4：先弹出 5，scc_id=1；再弹出 4，scc_id=1。SCC1={4,5}。
• 返回 3，3 的邻接处理完，low[3]=1 != dfn[3]=3，不弹出。返回 2。
• 2 的邻接处理完，low[2]=min(2, low[3]=1)=1。返回 1。
• 1 的邻接处理完，low[1]=min(1, low[2]=1)=1。low[1]==dfn[1]，弹出直到 1：弹出 3、2、1，SCC2={1,2,3}。

最终 SCC 数量为 2。注意 3->1 这条边是关键，它让 3 的 low 降为 1，随后层层上传，让 1 成为整体的根。4 和 5 是独立的双向环，所以单独成团。

这个例子里有个细节：4 在递归过程中，3 的 low 已经变成 1，但 4 的 low 始终是 4，因为 4 没有路径回到 3 所覆盖的更大环。所以 Tarjan 的处理是“各自为政”，只有在同一个强连通分量里才共享 low 的回溯能力。

4. 常见问题与调试心得

4.1 为什么low[v]取min时要区分邻接点是否在栈中

这是初学者最常踩的坑。很多人会写成这样：

} else { low[v] = min(low[v], dfn[u]); }

也就是不管 u 是否在栈中，只要 u 被访问过就用 dfn[u] 更新。这种写法在部分数据上也能出对答案，但遇到复杂图就会出错。原因在于：如果 u 已经被访问过且已经不在栈中，说明 u 所属的 SCC 已经被完整弹出，u 和当前 v 之间存在的边要么是通向过去已完结分量的边，要么是压根无法返回的横叉边。强行把 low[v] 拉低，会让 v 误以为自己能回到更早的节点，从而在回溯到“假根”时错过正确的弹出时机，导致同一个 SCC 被切碎，或者不同 SCC 被错误合并。

区分 in_stack 的本质是：我们只关心那些“当前仍有可能与 v 同处一个未完结分量”的点。已经在栈里的点，代表它还在等待自己的老大（分量根）出现，这符合“未完结”的定义；已经出栈的点，说明它的分量已经找到了根并截断，之后再遇到的边就是跨分量边，不能用于回溯。

4.2 什么情况下一个点单独成为一个强连通分量

如果一个节点没有任何能回到自己祖先的路径，那么它的 low 就会始终等于 dfn。最常见的情况是：该节点没有出边（只入不出），或者它的所有出边都指向当前尚未访问的节点但那些节点也无法回到它，或者出边指向的对象都已出栈。当 DFS 回溯到它时，low == dfn，它就会单独弹出一个 SCC，该 SCC 大小为 1。

这不代表算法出错了。在有向图中，任何单个节点都天然和自己强连通，所以一个孤立的点、一个入度出度都不匹配的点、一个 DAG 中的普通节点，都会单独成 SCC。Tarjan 并不保证“尽量合并”或者“尽量分开”，它只是按数学定义严格划分。

4.3 边界条件和递归深度问题

Tarjan 是递归实现，对于节点数超过十万的链状图，递归深度很容易超过系统栈限制。这时候有两个方案：一是在编译/运行环境中加大栈空间（例如 Linux 下用ulimit -s unlimited，或者在某些 OJ 上用#pragma comment(linker, "/STACK:102400000,102400000")）；二是手写栈模拟 DFS。手写栈的写法更繁琐，但能彻底避免系统栈溢出。

另外一个边界：图可能不连通。所以主循环必须遍历所有节点，对每个dfn[i] == 0的点调用 tarjan。如果不加这个循环，掉进一个孤立的子图里，算法就不会完整执行。

调试 Tarjan 最有效的方法是打印每个节点的 dfn、low 以及在栈中的状态，跟踪递归进入和返回的过程。我常用的一套打印策略是：

void tarjan(int v) { dfn[v] = low[v] = ++timer; st.push(v); in_stack[v] = true; cerr << "enter: " << v << " dfn=" << dfn[v] << " low=" << low[v] << endl; // ... cerr << "leave: " << v << " low=" << low[v] << " dfn=" << dfn[v] << endl; if (low[v] == dfn[v]) { // 弹出打印 } }

这样能直观看到每次低值更新的来源，比瞎猜快得多。

5. 从强连通分量到更多Tarjan扩展

5.1 求桥和割点

Tarjan 的思想不止用于有向图。在无向图中，同样基于 dfn 和 low，可以求桥（割边）和割点（关节点）。无向图中不需要栈，因为连通性是对称的，但需要额外记录父亲边，防止把已经走过的无向边当成回边反向使用。

求割点的规则：

• 对根节点，如果它的 DFS 子树数量大于等于 2，则它是割点。
• 对非根节点 v，如果存在某个子节点 u，使得 low[u] >= dfn[v]，则 v 是割点。含义是 u 的子树中没有一条边能绕过 v 连接到更上面的祖先，因此移除 v 会切断 u 所在子树。

求桥的规则：

• 对于边 v-u（u 是 v 的孩子），如果 low[u] > dfn[v]，则这条边是桥。注意是严格大于，因为哪怕能回到 v 本身，边 v-u 也不算桥（移除它不影响 v 和 u 的连通？实际上回到 v 意味着有另一条路径，所以不是桥）。

这里的 low 定义和有向图中略有差异，但整体节奏一致。理解强连通分量版本的 Tarjan 后，学桥和割点只需要半小时。

5.2 离线求LCA

Tarjan 还有一个知名的应用场景是离线求最近公共祖先。核心做法是把所有查询先存下来，然后进行一次 DFS，在遍历过程中用并查集维护已经访问完的子树。当访问到某个节点时，处理所有关联查询，如果另一个节点已经被访问过，那么它所在并查集的当前根就是 LCA。

这个方案虽然也叫 Tarjan，但机制上跟 SCC 版本有很大区别，它不依赖 dfn 和 low，而是“回溯时合并并查集”的思路。个人观点是，把这两个东西分清楚比较好，别混为一谈。如果面试官问到 Tarjan 算法，建议先确认他说的是强连通分量还是 LCA，再针对性回答。

5.3 缩点后的实际用途

求完 SCC 之后，最常见的后续操作是缩点。做法很简单：遍历所有边 (u, v)，如果 scc_id[u] != scc_id[v]，就在新图中添加一条从 scc_id[u] 到 scc_id[v] 的边。新图必定是一个 DAG，因为如果新图中有环，那环上所有 SCC 应该合并为一个更大的 SCC，这与 SCC 的极大性矛盾。

缩点后的 DAG 可以做很多事情：

• 求入度为 0 的 SCC 数量，判断是否所有点都能从某些源点到达。
• 做拓扑排序，执行动态规划最大值、计数、最优路径等。
• 2-SAT 问题里，判断完无解后还可以在缩点 DAG 上拓扑序输出一组可行解。

我在实际工程里用过一次缩点来处理模块依赖。当时一个系统有几百个模块，存在非常隐蔽的循环依赖，直接看调用关系很难发现。把调用关系建成有向图后跑 Tarjan，瞬间找出了三个强连通分量，每个都对应一组互相调用的模块，再人工审查代码定位到原因，非常高效。

6. 写在最后：我对Tarjan算法的一点体会

Tarjan 算法的魅力在于：它只用了一次 DFS，就把有向图里所有强连通分量完全切分，时间复杂度 O(N+M)，空间复杂度 O(N)。相比于先求传递闭包再合并的朴素做法，复杂度从 O(N^3) 甚至更高直接降到线性，这种效率上的飞跃是它成为经典的根本原因。

我踩过最深的坑就是写错else if (in_stack[u])这个分支。有一次在线上数据里死活差一个分量，打印了很久才发现漏掉了 in_stack 判断，导致一个已经完结的分量又“回溯”到了更早的节点。从那以后，我每次写 Tarjan 都会先默念一遍：树边更新 low[u]，回边更新 dfn[u]，出栈的边直接忽略。如果你也卡在某个案例上，不妨按这个思路逐条检查。

另外一个小技巧：如果只是想判断一个有向图是否有环，可以直接用 DFS 三色法，没必要上 Tarjan。但如果你需要分析环的构成、需要把环缩成点，Tarjan 就是最顺手的工具。学算法不是为了炫技，而是要在合适的场景拿出最匹配的方案，Tarjan 正是有向图分析工具箱里那把最锋利的刀。