Tarjan算法详解：从强连通分量到割点、桥与离线LCA

很多搞过竞赛或者刷过题的朋友应该都听过 Tarjan 算法的大名。第一次接触的时候看着那段短短的递归代码配上 dfn、low、栈这三个东西不少人是懵的为什么这样就能找出一堆互相可达的点为什么代码那么短却看起来那么难懂我当年也是啃了很久踩了不少坑才终于把它的运行过程在脑子里跑通。这篇文章我把自己的理解完整捋一遍不光是强连通分量还会把桥、割点、离线 LCA 这些同源扩展一并聊清楚希望能帮你真正把 Tarjan 算法装进脑子里而不是只会背代码。Tarjan 算法本质上是一套基于深度优先搜索的图连通性分析工具最经典、最核心的用途是求有向图的强连通分量。学懂它意味着你会用 O(NM) 的时间复杂度拿到图中所有“环上互相可达”的点集这对解决有向图中的判环、缩点、依赖分析、条件环检测等问题都是致命武器。适合正在学图论算法、准备面试或者竞赛、以及需要处理复杂依赖关系的数据工程师、底层技术人员参考。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 能否到 CA-B-C能。从 C 能否到 AC-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 求强连通分量的完整流程拆成下面几步从任意未访问节点出发执行 DFS。每个节点首次进入时初始化 dfn[v] low[v] 时间戳计数器并将 v 入栈。遍历 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]这是很多初学者最容易写错的地方。递归返回后检查 low[v] 是否等于 dfn[v]。如果相等说明 v 是某个强连通分量的根于是不断从栈顶弹出节点直到弹出 v 为止这些节点构成一个 SCC。继续遍历其他未访问节点直到所有节点都被处理。步骤 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; vectorint g[MAXN]; int dfn[MAXN], low[MAXN], scc_id[MAXN]; int timer 0, scc_cnt 0; stackint 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 是否未访问过如果没访问过就深入递归回传后更新 lowelse 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 开始 DFS1: dfn1, low1入栈。1-2: 2 未访问递归到 2dfn2, low2入栈。2-3: 3 未访问递归到 3dfn3, low3入栈。3-1: 1 已访问且在栈中low[3] min(3, dfn[1]1) 1。3-4: 4 未访问递归到 4dfn4, low4入栈。4-5: 5 未访问递归到 5dfn5, low5入栈。5-4: 4 已访问且在栈中low[5] min(5, 4) 4。5 的邻接遍历完low[5]4 ! dfn[5]5不弹出。返回 4。4 的邻接只剩一个接收 low[5]4low[4] min(4,4)4。low[4]4 ! dfn[4]4相等所以弹出栈顶到 4先弹出 5scc_id1再弹出 4scc_id1。SCC1{4,5}。返回 33 的邻接处理完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、1SCC2{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-uu 是 v 的孩子如果 low[u] dfn[v]则这条边是桥。注意是严格大于因为哪怕能回到 v 本身边 v-u 也不算桥移除它不影响 v 和 u 的连通实际上回到 v 意味着有另一条路径所以不是桥。这里的 low 定义和有向图中略有差异但整体节奏一致。理解强连通分量版本的 Tarjan 后学桥和割点只需要半小时。5.2 离线求LCATarjan 还有一个知名的应用场景是离线求最近公共祖先。核心做法是把所有查询先存下来然后进行一次 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(NM)空间复杂度 O(N)。相比于先求传递闭包再合并的朴素做法复杂度从 O(N^3) 甚至更高直接降到线性这种效率上的飞跃是它成为经典的根本原因。我踩过最深的坑就是写错else if (in_stack[u])这个分支。有一次在线上数据里死活差一个分量打印了很久才发现漏掉了 in_stack 判断导致一个已经完结的分量又“回溯”到了更早的节点。从那以后我每次写 Tarjan 都会先默念一遍树边更新 low[u]回边更新 dfn[u]出栈的边直接忽略。如果你也卡在某个案例上不妨按这个思路逐条检查。另外一个小技巧如果只是想判断一个有向图是否有环可以直接用 DFS 三色法没必要上 Tarjan。但如果你需要分析环的构成、需要把环缩成点Tarjan 就是最顺手的工具。学算法不是为了炫技而是要在合适的场景拿出最匹配的方案Tarjan 正是有向图分析工具箱里那把最锋利的刀。