Tarjan算法详解：强连通分量、dfn与low、缩点建DAG全攻略

简介一份关于有向图强连通分量SCC求解的算法学习文档适合正在学习图论、准备算法竞赛或复习数据结构的中高级读者。文档以Tarjan算法为主线从强连通分量定义讲起结合示意图逐步演示DFS搜索、堆栈操作与DFN/LOW数组更新过程并给出完整C实现代码及时间复杂度分析。资源为docx格式整包仅1个文件、约185KB便于直接打开阅读或打印。目前已有480人学习下载。借助文档中的实例图、代码与后续优化建议读者可清晰理解Tarjan算法的执行流程并快速应用到自己的项目中是掌握这一经典算法的实用参考资料。 最近整理算法笔记把Tarjan求强连通分量这份docx重新翻出来改了一遍顺带把注释补全了。这东西在ACM、LeetCode题解里出镜率极高也是面试时区分“背过板子”和“真懂图论”的常见考察点。如果你正在学有向图、被“强连通分量scc”这个概念绕晕过或者看代码能看懂但要自己推导时总觉得差一口气这篇应该能帮你把那层窗户纸捅破。我不会只贴一段模板代码就完事而是把dfn、low、栈、缩点这些关键设计的来龙去脉交代清楚尽量做到看完之后再遇到变种题你能自己推而不是翻笔记。1. 有向图里的“一团死磕到底”的节点组强连通分量到底是什么1.1 从一个生活场景理解scc想象一支传销团队规则是每个人只能把资料递给名单上指定的人但传递方向是单向的。如果A能把资料传到B手里B也能把资料传回A手里那这两个人之间就是互相可达的。再极端一点如果团队里有那么一小撮人内部你传我、我传你怎么传都出不了这个圈但圈外的人传进来就再也没法传出去这一小撮人就是一个强连通分量。用图论术语说在有向图G中如果两个顶点u、v互相都存在从u到v和从v到u的路径就说u和v是强连通的。把这种强连通关系视为一种“等价关系”它会把顶点集划分成若干个不相交的子集每个子集内部的任意两点都互相可达这些子集就是强连通分量简称scc。要注意单个顶点自身当然是强连通的路径长度为0也算所以每个顶点至少属于一个scc。这也是后面算法里边界情况的基础——一个孤立点本身就是个只有自己的scc。1.2 为什么不能用“从每个点BFS/DFS”的笨办法新手最容易想到的暴力思路对每个顶点做一次DFS或BFS看它能到达哪些点再反过来看哪些点能到达它取交集。这种做法理论可行但复杂度是O(n*(nm))稠密图直接爆炸。更关键的问题在于暴力法只能判断两个点是否互相可达很难高效地把所有scc一次性“切”出来。你想像一下一个1000个点、50000条边的图对每个点跑一遍全图遍历那就是5000万次访问虽然勉强能跑但如果是1e5个点、1e6条边的竞赛图论题直接超时。所以才需要Tarjan它只跑一遍DFS时间复杂度O(nm)线性搞定全部强连通分量。这个效率差异就是算法存在的意义。1.3 Tarjan算法到底在干什么Tarjan算法的核心思想非常朴素在深度优先搜索树中利用一个辅助栈把“正在探索中、尚未确定归属”的顶点压进去通过两个关键时间戳dfn和low来判断什么时候栈顶的一段连续区域可以整体弹出来——那就是一个完整的scc。这里我不急着给定义先打个比方。你在一座迷宫里做标记每到一个新房间就编个号dfn同时记一下“我这个房间所能回退到的最小编号”low。如果你发现某个房间的dfn等于low说明从它出发绕一圈最远只能回到它自己它就是这个连通块的老大此时栈里从它往上的所有房间都是同一个连通块的成员全部弹出。这个“dfn等于low即弹出”的判断标准是整个算法的灵魂。2. 手把手拆解Tarjandfn、low与栈的三角关系2.1 dfn和low的含义必须用大白话讲透dfn[u]顶点u被DFS首次访问的时间戳从1开始递增每个顶点唯一。你可以理解成“进门编号”。low[u]从u出发经由u的子树内任意顶点再通过最多一条“非树边”回边或横叉边能够到达的顶点的最小dfn值。听起来绕但实际更新规则很简单初始化low[u] dfn[u]遍历u的所有邻接点v若v未被访问过对v做DFS回溯后更新low[u] min(low[u], low[v])若v已被访问过且v还在栈中更新low[u] min(low[u], dfn[v])若v已被访问过且不在栈中说明v所在的scc已经处理完毕直接忽略。这里最容易被误解的是第二条为什么不是min(low[u], low[v])而是min(low[u], dfn[v])道理在于v已经被访问过且在栈中说明v是u的祖先或祖先侧的点u可以通过这条边回到更靠近根的节点。我们用dfn[v]作为参考值而不是low[v]是因为low[v]可能已经被更新到了比dfn[v]更小的值——那说明v已经能连到更上面的节点此时取dfn[v]并不影响正确性但取low[v]在某些情况下可能导致low值被错误地“压缩”。你记住一句话访问到还在栈中的点时用dfn更新访问到未访问的点时用low更新。2.2 栈的作用以及为什么不直接用一个数组标记很多初学者会问为什么非得用栈我用一个布尔数组inStack标记顶点是否在“当前DFS路径”上不行吗答案是不行。inStack只能表示“这个点正在被访问”但Tarjan需要的是“这个点还没归入任何一个scc”。仔细想一下DFS是一条路走到黑再回溯的当一个子树的DFS完成时如果它构成一个scc那么这些点应当被一起弹出。如果只用一个布尔数组你无法方便地维护“从某个祖先节点一路延伸到当前节点的连续节点集合”——这个连续集合恰好对应栈中从某个位置到栈顶的一段。栈的另一个好处是当dfn[u] low[u]时从栈顶一直弹到u弹出的节点顺序恰好构成一个scc而且这个scc在栈中是连续的一段。这个连续性是由DFS递归结构天然保证的换成其他数据结构反而要额外维护关系。2.3 完整C实现附逐行解释以1为起始顶点编号图用邻接表存储这是最通用的写法#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint G[MAXN]; // 邻接表 int dfn[MAXN], low[MAXN], sccId[MAXN]; bool inStack[MAXN]; stackint st; int dfsClock 0, sccCnt 0; void tarjan(int u) { dfn[u] low[u] dfsClock; st.push(u); inStack[u] true; for (int v : G[u]) { if (!dfn[v]) { // v没被访问过属于u的子树先深搜再回溯更新low tarjan(v); low[u] min(low[u], low[v]); } else if (inStack[v]) { // v被访问过且在栈中说明v是u的祖先或祖先方向的点 low[u] min(low[u], dfn[v]); } // 如果v已访问但不在栈中说明v所在的scc已经处理完忽略 } // 关键判断u是一个scc的根 if (dfn[u] low[u]) { sccCnt; int v; do { v st.top(); st.pop(); inStack[v] false; sccId[v] sccCnt; } while (v ! u); } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; G[u].push_back(v); } for (int i 1; i n; i) { if (!dfn[i]) tarjan(i); } cout scc数量: sccCnt endl; for (int i 1; i sccCnt; i) { cout scc i : ; for (int j 1; j n; j) { if (sccId[j] i) cout j ; } cout endl; } return 0; }整个过程的执行逻辑是对每个未访问节点启动一次tarjan在递归中维护dfn、low和栈当dfn[u] low[u]时从栈顶弹出直到u为止的所有节点归入新的scc。这段代码有一个小地方值得单独提主循环里对每个未访问节点调tarjan。这保证了即使原图是不连通的也能处理完所有节点这也是有向图比无向图麻烦的地方——无向图的连通分量通过一次DFS就能搞定有向图必须考虑方向所以这个外层循环是必要的。3. 算法正确性直觉为什么dfn等于low就一定是一个scc的根3.1 从DFS树角度理解四条边一个有向图的DFS过程会在原图上生成一棵DFS树如果图不连通则是森林。根据边的方向可以把原图的边分为四类树边tree edgeDFS中实际递归遍历的边回边back edge从后代指向祖先的边前向边forward edge从祖先指向非直接后代的边横叉边cross edge连接两个不存在祖先后代关系的子树的边。Tarjan算法的精髓在于一个scc内部的节点在DFS树中一定不是散落分布的而是可以从某棵子树的根节点开始通过树边连接到所有成员同时这个scc与外部的连接要么没有回边到祖先要么有回边但无法追溯到比根更早的祖先。当low[u] dfn[u]时意味着以u为根的子树中没有任何一条边能走到比u更早被访问的节点。那么u就是这棵子树中能到达的最“上面”的节点也就是这个连通块的根。从栈里u以上的所有节点都是u的子树中通过树边能到达、且互相连通的节点它们构成了一个scc。3.2 为什么栈顶到u的节点恰好是一个完整scc关键点当u的DFS结束且满足弹出条件时栈中从u到栈顶的所有节点是在u的子树中尚未归类的节点。这些节点之间必然互相可达对任意两个节点a、b因为它们在栈中且位于u的子树内所以从u可以到a和b又因为low[u] dfn[u]意味着这个整体内部不存在能绕出u子树的边所以a和b之间能通过u“中转”相互到达u到ab到u虽然方向需要仔细论证但直觉上这个整体内部是强连通的。严谨来说这个结论依赖这样一个事实在u的DFS子树内部凡是还没归入其他scc的节点彼此之间通过树边和回边形成了强连通闭环。这正是弹栈时一次性弹出的依据。3.3 一个可手推的示例图看这个图1 - 2 2 - 3 3 - 1 到这里1、2、3形成一个环 3 - 4 4 - 5 5 - 4 4、5形成二节点环假设从1开始DFS访问顺序是1、2、3、4、5dfn[1]1, low[1]1dfn[2]2, low[2]2dfn[3]3, low[3]33连向1在栈中故low[3]min(3, dfn[1])13再访问4dfn[4]4, low[4]44连向5dfn[5]5, low[5]55连向4在栈中low[5]min(5, dfn[4])45回溯low[4]min(4, low[5])4dfn[4]low[4]4弹出4和5scc{4,5}回到3low[3]min(1, low[4]4)1回到2low[2]min(2, low[3]1)1回到1low[1]min(1, low[2]1)1dfn[1]low[1]1弹出1、2、3scc{1,2,3}注意弹出顺序{4,5}先弹出{1,2,3}后弹出。这正好说明Tarjan求出的scc顺序是逆拓扑序——从“深处”的scc先弹出越靠近“入口”的scc越晚弹出。这个性质在后面的缩点DP里非常有用后面会再提。4. 实操中的常见问题栈溢出、初始化、与Kosaraju的对比4.1 递归深度过大时的栈溢出问题与处理Tarjan常规写法是递归DFSPython等语言在面对10万级别链状图时递归深度容易爆栈C在极端情况下也会出现调用栈溢出。一个比较实用的处理方法是用显式栈模拟递归把DFS过程改写成迭代式。但说实话这种方式会让代码可读性大幅下降竞赛里一般不这么干。更推荐的做法是C在main开头加一句ios::sync_with_stdio(false);提升输入效率同时把递归形式保留竞赛题的递归深度一般不致命除非是毒瘤出题人Python用sys.setrecursionlimit(1000000)提高递归上限或者提前用threading.stack_size()开大线程栈。如果实在遇到深度特别大的图比如5e5个点组成的链建议直接改用Kosaraju算法它是两次DFS但第二次用的是反向图也可以用显式栈实现避免递归。4.2 初始化细节dfn和low都初始化为0dfn初始化为0的意义0代表“未访问”。因为时间戳从1开始所以0天然是未访问标记不需要额外的visited数组。这是很多人容易忽略的写法巧思——你少一个bool数组代码更简洁但代价是你必须保证dfsClock从1开始递增并且永远不回退。low初始化为0没有意义真正起作用的是在进入tarjan时先给low赋成dfn的值所以申明时置0也无所谓。但强推一种习惯所有全局数组申请后默认置0这也是为什么很多模板里看不到显式初始化直接用全局变量的原因。4.3 Tarjan vs Kosaraju怎么选Kosaraju的思路是先对原图做一次DFS得到出栈顺序再在反向图上按出栈逆序做DFS每次能访问到的点集就是一个scc。它简单易懂但需要两个图原图和反向图空间翻倍且因为要两次DFS常数略大。Tarjan只需要一次DFS空间也更省并且求出的scc顺序是逆拓扑序这个性质在缩点DP中直接省去一次拓扑排序。对比下来对比维度TarjanKosaraju时间复杂度O(nm)O(nm)DFS次数1次2次额外空间一个栈原图反向图实现难度较难理解容易理解附带性质scc编号为逆拓扑序顶点出栈顺序可用实战中如果只是求scc数量或划分两者都能用如果后面要做缩点DP或缩点拓扑排序Tarjan因为自带逆拓扑序会更顺手。4.4 关于“重边”到底要不要处理有向图可能存在重边两条或更多完全相同的边。很多人担心重边会影响Tarjan的判断。结论是不影响。因为重边本质上没有提供新的可达关系一个顶点通过重边能到达的目标点和通过单条边能到达的目标点完全一致。Tarjan的更新只关心“能否到达”不关心“有几条路径”所以重边可以直接忽略。但如果你的邻接表存了重边DFS时会对同一个v进行多次重复判断只是多几次无用的循环不影响结果。反过来如果你在缩点后建新图重边会导致新图中边的重复计数这在统计出度入度时会造成误差需要去重。这也是做题时常见的一个坑。5. 进阶玩法缩点后建DAG解决一大波图论题5.1 缩点是什么以及为什么缩完就是DAG把每个scc看成一个“超级节点”如果原图中存在从scc A中的某个点指向scc B中某个点的边就在超级节点A和B之间连一条有向边。因为tarjan弹出的scc顺序是逆拓扑序所以按sccId编号建新图的时候边的方向自然是从编号大的scc指向编号小的scc或者反过来取决于你建图时怎么连。这个新图一定是有向无环图DAG。为什么因为如果新图里有环那么这个环上的所有超级节点对应的原图节点集合会互相可达它们应该被合并成一个更大的scc这违反了scc的极大性定义。这个性质的价值在于DAG上的问题比有向图上的问题好处理得多可以做动态规划、拓扑排序、贪心等而有向图不能直接这么做。5.2 一个经典例题判断“所有点都能到达的点”的个数有个很经典的题如洛谷P2341受欢迎的牛给一个有向图求有多少个点使得从任意点出发都能到达它。暴力做是不可行的。正确解法先用Tarjan缩点得到DAG在DAG上如果一个超级节点能被所有节点到达那它就是该DAG唯一的出度为0的节点更准确说是唯一没有出边的节点且全图连通到这个汇点统计出度为0的scc数量如果恰好为1答案就是该scc的大小原图中节点数量如果大于1说明没有符合条件的节点答案为0。这个过程的巧妙之处在于缩点把“任意点可达某点”的问题转化成了DAG上“唯一汇点”的问题后者的判定只需一步出度统计O(nm)。这就是学Tarjan的真正价值——它是很多图论综合题的起手式。5.3 缩点后scc编号自带逆拓扑序省一次拓扑排序前面提到Tarjan弹出的scc顺序是逆拓扑序这意味着什么呢比如在求DAG最长路的时候本来需要先拓扑排序再DP现在可以直接按照scc编号从大到小或从小到大遍历直接完成递推。举一个实际场景如果缩点之后你得到sccA指向sccB的边那么tarjan运行结果是sccB的编号一定小于sccA因为B先弹出。所以如果你按编号从小到大的顺序遍历scc你其实是在按照拓扑序处理。换句话说你连拓扑排序的代码都不用写了。这个细节很多人不知道甚至不少竞赛选手都是直接用Kahn拓扑排序再处理。掌握这个性质你在处理涉及缩点DP的题目时可以少写一个函数而且不容易错。5.4 实战推演缩点后的转移方程假设有一个有向图每个点都有权值求一条路径能获得的最大权值和路径可重复经过点但权值只算一次。这个题直接在有向图上没法DP因为有环会导致无限循环。但缩点后问题就变成了DAG上每个scc有权值内部所有节点权值和找一条路径使得经过的scc权值和最大。转移方程就是经典的DAG最长路dp[v] max(dp[v], dp[u] weight[v])其中u指向v因为有自带的逆拓扑序我们甚至不需要额外排序。代码上可以直接对sccId从小到大循环利用边的方向同步更新。实际跑下来非常稳健这也是为什么Tarjan在竞赛图论题里几乎是必背算法。6. 调错心法我踩过的坑和排查思路6.1 最常见的坑误用栈外点的dfn去更新low新手最容易写错、而且错了很难发现的问题就是在遇到“已访问但不在栈中”的边时错误地用dfn[v]更新low[u]。举个例子如果v已经归入某个scc并弹出栈这时用dfn[v]把low[u]拉得很低导致u这边形成错误的连通关系最终弹栈时把不属于同一scc的节点混在一起。判断方法很简单看inStack[v]只有为true时才允许用dfn[v]更新。少了这个判断结果全错而且样例往往还是很小的图很难一眼看出来。6.2 递归爆栈的备战方案竞赛中如果题目明确说n可以达到1e6别侥幸用递归。虽然Tarjan理论上O(nm)很优秀但递归深度一上来C在Windows下默认栈大小只有1MB左右很容易崩。我的个人习惯是如果题目规模在2e5以上果断改成Kosaraju或者提前查平台支持用非递归的Tarjan实现。平时练习可以写一个非递归版本练手真到了赛场上就会庆幸自己提前准备过。另外一个小经验在本地调试时如果发现“明明逻辑没错但一直段错误”优先怀疑栈溢出先把递归深度小数据测一下再把n放到最大值试跑基本能定位。6.3 建图阶段的方向错误Tarjan对有向图的方向极其敏感。有一条边方向写反最终scc划分就完全不同。在缩点题里方向写反还可能导致DAG拓扑方向完全颠倒DP结果错误。所以每次建图时我会专门检查边的起点和终点是否和题意一致。尤其是那种“u能到v”的表达有时候题目会写成from u to v有时反过来稍不留神就反了。6.4 栈残留导致重复归属错误在一个节点多个scc之间反复调试时如果sccId数组没有清空或者上一次运行的数据残留在本地变量里比如全局变量没有重置下一次样例可能直接把上一轮的编号当作本轮结果输出会出现莫名其妙的大数字。在竞赛环境中全局变量默认置0但如果你用的是类封装或封装函数一定要记得每次运行前清空dfn、low、sccId、inStack等数组。我遇到过好几次因为sccId没重置本地样例全过交上去全错的惨案排查了半小时才发现是初始化问题。7. 结尾一点个人经验Tarjan算法我前后手写过不下几十遍但真正让我理解透的不是背代码而是拿小图一步步手动模拟弹栈过程。每次把“栈顶到u弹出”这个动作画在纸上对low和dfn的理解就会加深一层。如果你现在正处于“会写但不懂”的状态我建议你找几个小图自己当CPU手推一遍dfn、low和栈的变化比看十篇博客都有用。另外一个更实用的建议把这份docx里的代码模板改造成自己习惯的风格比如用数组模拟栈代替std::stack存成模板文件。这样刷题时直接复制再把注意力放到建图和解题上。算法模板这东西平时多准备几个版本不吃亏真要比赛时你根本没时间从零写。最后再提一句延伸方向学会Tarjan之后可以接着学一下2-SAT问题、无向图的割点和桥用差不多的dfn、low思路以及双连通分量。这条线走通了图论的连通性这块基本就稳了很多看起来吓人的难题剥开外壳都是缩点后的DAG操作。本文还有配套的精品资源点击获取