割点、桥与双连通分量：从Tarjan原理到实现全解析

我在刷图论题的时候第一次看到“割点”“桥”“双连通分量”这几个词脑子里是懵的明明一个很简单的无向图为什么非要分成这么多概念但后来真正上手做网络可靠性分析、求环、判断一个图能不能“分开拉走”这类问题之后才发现这套东西是理解无向图连通性的核心也是 Tarjan 算法里最经典的一类应用。这篇博客我就把自己从“会背模板”到“真懂原理”的过程整理出来把割点、割边桥、点双连通分量v-DCC、边双连通分量e-DCC一条线讲清楚。这篇文章适合刚学完 DFS 和图论基础、想去挑战连通性进阶题的人也适合像我一样学过 Tarjan 但总是把点双和边双搞混的人。我会从 DFS 树开始讲把每一个判定条件都给你解释出“为什么”然后给出可直接抄的 C 实现最后再聊聊那些让你 WA 到怀疑人生的坑。1. 先想清楚你在技术上到底要解决什么问题1.1 一个图为什么会“断”割点和桥的直觉先抛开术语看图的最根本问题连通性。一个无向图是连通的意思就是任意两个点之间都能走通。但更关键的是这个“连通”有多稳固如果你拆掉某个点图还连不连通如果你拆掉某条边图还连不连通这里就有两种“拆法”拆点把一个顶点包括它关联的所有边删掉图是否分裂成多个连通块拆边只删一条边图是否分裂成多个连通块如果一个点被删掉之后图的连通块数量变多了那这个点就叫割点。同理一条边被删掉之后连通块数量变多这条边就叫割边也叫桥。我记这个概念时用过一个生活类比想象一座城市里有若干路口和道路所有路口之间都能到达。割点就是那种“必经之路口”一旦发生事故封路城市就被分成两半互相过不去。桥更直观——就是那条唯一连接两岸的桥桥断了两岸直接失联。注意一个细节如果删掉某个点图只是少了一个孤立点而连通块数没有增加那这个点不是割点。比如一个孤零零的叶子节点去掉它图剩下部分还是连通的连通块数没变它就不是割点。所以判断标准永远是“连通块数量变多”不是“图变得不连通了”。1.2 什么时候需要求割点和割边这类问题的典型应用场景我列几个最常见的网络可靠性通信网、电网里某些节点或链路坏了整个网络会不会瘫痪需要找出关键节点、关键线路。环的判定与提取无向图的桥边一定不在任何环里配合双连通分量能帮你理解图的环结构。缩点建图把边双连通分量、点双连通分量缩成一个点把原图缩成一棵树树上问题就好做多了。比如“至少加几条边让图变成边双连通”这类经典题本质就是求边双缩点之后叶子节点的数量。题解的底层依赖很多看似和双连通无关的题先求一遍割点或双连通后面就迎刃而解。1.3 双连通分量和“连通分量”有什么区别如果你已经知道什么叫无向图的连通分量那双连通分量就是在此基础上加了个“韧劲”的概念边双连通分量e-DCC一个极大子图删掉其中任意一条边子图仍然连通。点双连通分量v-DCC一个极大子图删掉其中任意一个点子图仍然连通。注意点双连通的定义其实要更精细一些我们到第 6 节再展开但你可以先记住一句通俗的话边双可以理解为“没有桥的极大连通区域”点双可以理解为“没有割点的极大连通区域”。这里有个非常容易误会的点点双连通和边双连通没有绝对的包含关系。一个子图是点双连通的它一定是边双连通的吗不一定。比如两个点之间两条平行重边构成的图它是边双连通的但对两个点来说删掉其中任意一个点剩下的就是一个孤立点严格来说它并不是点双连通的两个点的特殊情况在定义里有争议竞赛里通常单独处理。所以不要把他们当成同一个东西后面代码也不是一套。2. Tarjan 算法基石DFS 树、dfn 和 low2.1 从 DFS 开始把图“拉直”成一棵树所有割点、桥、双连通分量最经典的解法都是基于深度优先搜索DFS的 Tarjan 算法。核心思想是用 DFS 去遍历整个图在这个过程中记录每个点第一次被访问到的时间并计算一个所谓的 low 值最后用 dfn 和 low 的关系来判断割点、桥。为什么 DFS 这么好用因为 DFS 在无向图上跑的时候会产生一棵 DFS 树。树的边分为两类树边DFS 实际走过的边也就是从某个点第一次发现新节点时走的那条边。回边其余没被走过的边它们连接某个点和一个已经在 DFS 栈里的“祖先”。很多人学 Tarjan 卡在这一步是因为没意识到一个关键性质在无向图的 DFS 中不存在“横叉边”。通俗讲你从某个节点出发通过 DFS 第一次访问到的节点一定是树边上的后代如果一条边连到了一个已经访问过的节点且它不是父节点那它一定连回的是祖先节点不是兄弟子树里的节点。这个性质是 Tarjan 算法在无向图上成立的基础。2.2 dfn 与 low 到底怎么算dfn[u]有的视频里叫 time、num意思是节点 u 第一次被 DFS 访问到的序号。相当于给每个节点发一张“进山顺序”号码牌从 1 开始递增。low[u] 是整棵 DFS 树里最重要的量含义是从 u 出发只通过 u 的子树中的节点最多能回溯到的“最老”节点序号最小的 dfn。注意它包含两类路径从 u 出发沿着树边走到子树里的后代节点从某个后代节点出发走一条回边到达 u 的某个祖先。所以 low[u] 初始值就是 dfn[u]然后对每个邻接点 v如果 v 没被访问过就递归 DFS返回后用 low[u] min(low[u], low[v])如果 v 已经被访问过并且 v 在 DFS 栈里也就是 u 的祖先就用 low[u] min(low[u], dfn[v])。这里有个新手特别容易犯的错看到“访问过”就更新也不管 v 是不是祖先。在无向图里如果你直接用 low[u] min(low[u], dfn[v])回边会把父节点的情况也算进去导致 low 值普遍偏低判定结果全乱。正确做法是区分 v 是不是 u 的“直接父节点”从而跳过父边或者更严格地判断 v 是否在栈内。2.3 手动模拟一遍一分钟把 low 刷明白举个 6 个点的例子边集合为(1,2), (2,3), (3,1), (3,4), (4,5), (5,6), (6,4)。这个图里 1-2-3 构成一个环4-5-6 构成一个环中间靠 3-4 这条边连接所以 3 和 4 都是割点3-4 是一条桥。我们从 1 开始 DFS访问 1dfn[1] 1low[1] 1走到 2dfn[2] 2low[2] 2走到 3dfn[3] 3low[3] 33 的邻点1 已访问且在栈里用 low[3] min(3, dfn[1]) 1回到 2low[2] min(2, low[3]) 1回到 1low[1] min(1, low[2]) 1然后从 1 继续走 3但 3 已经访问过并且 3 是 1 的孙子不是父节点不再更新从 3 继续访问 4dfn[4] 4low[4] 4访问 5dfn[5] 5low[5] 5访问 6dfn[6] 6low[6] 66 连接到 4而 4 已访问且在栈里low[6] min(6, dfn[4]) 4回到 5low[5] min(5, 4) 4回到 4low[4] min(4, 4) 4回到 3low[3] min(1, 4) 1。最后结果low[1] 1low[2] 1low[3] 1low[4] 4low[5] 4low[6] 4。你看每个环里的节点 low 值趋同桥两端的 low 值有明显的“断裂感”这就是后续判定割点和桥的直觉来源。注意上面模拟我把“判断 v 是否在栈中”简化了。实际写代码时如果只是判父节点跳过也可以跑对大多数情况但遇到重边就会出问题后面第 4 节详细说。3. 割点判定规则与完整实现3.1 割点的核心判定现在来说怎么判断 u 是不是割点。在 DFS 树上分两种情况u 不是 DFS 树的根节点如果存在一个子节点 v满足 dfn[u] low[v]那么 u 是割点。u 是 DFS 树的根节点如果 u 有至少两个子节点那么 u 是割点。为什么 dfn[u] low[v] 就能判断呢low[v] 表示从 v 的子树出发最远能回到的“最老”节点。如果 low[v] 还是大于等于 dfn[u]说明 v 这颗子树里没有任何一条回边能绕过 u 到达 u 的祖先。那一旦删掉 u这棵子树和 u 的祖先部分就彻底分开了连通性被破坏所以 u 是割点。反过来说如果存在某个子节点 v 满足 dfn[u] low[v]说明 v 的子树里有一条回边能绕回 u 的祖先即使删掉 u子树 v 也能绕到别的路继续和上面保持连通那 u 就不是割点。3.2 根节点要单独处理根节点为什么特殊因为 dfn[root] 是最小的dfn[root] low[v] 天然恒成立按非根节点的判定逻辑根节点只要有一个子节点就会被判成割点那就错了。根节点只有拥有至少两个子树时才是割点删掉根它的这些子树之间互相没有边相连图就会散架。还有一个隐藏细节如果原图本身不连通需要对每个连通分量分别跑一次 DFS并对每个 DFS 树的根单独统计子节点数量。3.3 C 实现与易错点#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint G[MAXN]; int dfn[MAXN], low[MAXN], timer_; bool isCut[MAXN]; void tarjan(int u, int fa) { dfn[u] low[u] timer_; int childCnt 0; for (int v : G[u]) { if (!dfn[v]) { childCnt; tarjan(v, u); low[u] min(low[u], low[v]); if (fa ! 0 dfn[u] low[v]) { isCut[u] true; } } else if (v ! fa) { low[u] min(low[u], dfn[v]); } } if (fa 0 childCnt 2) { isCut[u] true; } } 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); G[v].push_back(u); } for (int i 1; i n; i) { if (!dfn[i]) { tarjan(i, 0); } } int cnt 0; for (int i 1; i n; i) { if (isCut[i]) cnt; } cout cnt endl; for (int i 1; i n; i) { if (isCut[i]) cout i ; } return 0; }这里我用fa 0表示根节点。每到一个邻接点先判断是不是dfn[v]为 0没访问过就走树边如果访问过并且 v 不是 u 的父亲就走回边更新 low。注意这个写法在无重边的图里是对的。但如果图里有重边比如两条 1-2 的边DFS 从 1 到 2然后 2 的所有邻点里有 1由于 v fa 会被跳过2 的 low 不会通过这条重边更新回 dfn[1]在某些题目里会误判割点或桥。处理方式我放到第 4 节讲桥的时候一起说。4. 桥割边判定规则与完整实现4.1 桥的核心判定桥的判定和割点长得像但细节不同。对于一条树边 (u, v)其中 u 是父亲v 是儿子如果满足low[v] dfn[u]那么这条边是桥。为什么不能取等号因为如果 low[v] dfn[u]说明 v 的子树里有回边能回到 u 本身。删掉边 (u,v) 之后v 还可以通过那条回边回到 u图还是连通的所以这不是桥。只有严格大于才说明子树里没有回边能回到 u 或者 u 的祖先删掉边后 v 的子树彻底脱离。对比一下割点的判定 dfn[u] low[v]你会发现桥和割点就差一个等号。这个等号的差异我当年记混了好几次后来干脆每次都推一遍删点之后点没了回边回到 u 本身也没用因为 u 已经被删了删边之后 u 还在回边回到 u 还能继续连通所以等号的情况不能算桥。4.2 重边处理很多人在这翻车如果图中存在重边直接按v fa跳过父边就会出问题。比如两个点 1 和 2 之间有两条平行边DFS 从 1 走到 2此时 2 看到邻点 1因为 1 是父节点被跳过low[2] 不会更新为 dfn[1]于是 (1,2) 会被判定成桥。但实际上删掉其中一条边另一条边还在图依然连通它不是桥。解决办法是DFS 时记录边的编号而不是只记父节点编号。具体做法是图存边带编号递归传入上一条边的编号in_edge当访问到邻边编号等于in_edge时跳过如果邻点访问过但边号不一样就用 dfn[v] 更新 low[u]。这样重边也能正确回传。4.3 割点 vs 桥的对比对比项割点桥割边判定条件树边 u-vdfn[u] low[v]low[v] dfn[u]删掉后的效果点及其相连边消失图可能分裂只删一条边图可能分裂根节点特殊处理根至少有两个子节点才是割点根不特殊正常判定重边影响通常无影响但如果重边导致跳过导致子树判断错误也有影响必须处理否则会把重边错判成桥桥的完整代码vectorpairint,int G[MAXN]; // {to, edge_id} int dfn[MAXN], low[MAXN], timer_; bool isBridge[MAXN]; void tarjan(int u, int in_edge) { dfn[u] low[u] timer_; for (auto [v, eid] : G[u]) { if (!dfn[v]) { tarjan(v, eid); low[u] min(low[u], low[v]); if (low[v] dfn[u]) { isBridge[eid] true; } } else if (eid ! in_edge) { low[u] min(low[u], dfn[v]); } } }这段代码里eid ! in_edge是关键它允许一条重边回到父亲节点因为那条边的编号和当前来的边编号不同说明存在另一条路low 可以正常被更新。5. 边双连通分量e-DCC与缩点5.1 求 e-DCC 的两种常见写法边双连通分量的定义是没有桥的极大连通子图。所以求法天然有两种思路。思路一先用 Tarjan 把所有的桥标记出来然后对整个图做一次 DFS/BFS遍历时禁止走桥边每个连通块就是一个边双连通分量。这个思路太好理解了代码也简单。思路二利用 low 值和栈。在 Tarjan 过程中把节点压入栈当发现桥时把栈中节点弹出来作为一个分量。实际上很多模板用low[u] dfn[u]判分量边界也能跑对。第一种思路更不容易写错我推荐新手先用它。5.2 缩点建新图求完 e-DCC 之后把每个分量看成一个新点原图中的每条桥边连接两个不同分量就变成新图中的一条边。因为原图中的桥不可能在环里所以缩点之后的新图一定是一棵树如果原图连通的话。这就是“无向图缩点变成树”的由来。缩点代码骨架int belong[MAXN], dccCnt; void dfs(int u) { belong[u] dccCnt; for (auto [v, eid] : G[u]) { if (belong[v] || isBridge[eid]) continue; dfs(v); } } // 主流程中 for (int i 1; i n; i) { if (!belong[i]) { dccCnt; dfs(i); } }然后遍历原图所有边如果belong[u] ! belong[v]就在新图里加边。这里注意如果原图有重边新图也可能出现重边但树这种结构里重边不常见不过统计叶子节点时要注意不要重复计数。为什么会用到缩点举一个经典例子求一个无向连通图至少加几条边才能变成边双连通图。答案是先缩点成树统计度数为 1 的节点数 leaf结果就是 (leaf 1) / 2。原理是每次加一条边可以连接两个叶子把树变成一个大环结构。6. 点双连通分量v-DCC与圆方树6.1 点双的性质点双连通分量的定义严格来说是一个极大子图满足子图中任意两个不同的点之间都存在至少两条“点不重复”的路径即点不相交路径。这句话翻译成人话子图里任意两个点都不在同一个“必经之点”的分界处删掉任何一个点这一坨仍然连通。为什么两个点的简单图只有一条边不算点双因为两个点之间只有一条路径删掉其中一个点另一个点孤立不符合任意删点后连通的属性。所以竞赛里常规定义点双至少要有 3 个节点或者单独特判两个点加一条边的情况有的题按点双算有的不算看题目描述。这个定义坑了我很久建议你做题前先看清楚题目对“点双”的处理规则。点双一个非常重要的性质是每条边恰好属于一个点双。但一个割点可以属于多个点双。6.2 怎么求点双求点双和求边双不一样不是简单标记完再 DFS 就能分出来的。因为割点会被多个点双共用。标准做法是用一个栈在 Tarjan 过程中维护“当前分量的点集合”。伪代码如下void tarjan(int u, int fa) { dfn[u] low[u] timer_; stk.push(u); for (int v : G[u]) { if (!dfn[v]) { tarjan(v, u); low[u] min(low[u], low[v]); if (dfn[u] low[v]) { // u 是割点v 的子树构成一个点双 dccCnt; do { w stk.top(); stk.pop(); belong[w].push_back(dccCnt); // 记录w属于哪个点双 } while (w ! v); belong[u].push_back(dccCnt); } } else if (v ! fa) { low[u] min(low[u], dfn[v]); } } }注意弹出节点的判断条件是w ! v不是w ! u。因为 u 可能属于多个点双所以不能把 u 弹出只把 u 记到这个分量的集合里。这个细节非常容易错我第一次写的时候弹出的条件是w ! u结果整个分量错乱。6.3 点双缩点圆方树点双缩点之后得到的结构叫圆方树。原图的点叫圆点每个点双分量建一个新点叫方点方点连接到它包含的所有圆点。这样原图就变成一棵树若原图连通树上问题的分析会变得很方便。圆方树在很多问题里都有用比如求无向图任意两点之间的“必经点”集合可以先建圆方树然后问题就变成树上路径问题。这个内容比较高级但理解点双求法之后再看圆方树会顺很多我建议把它作为进阶目标不用第一次就强求吃透。7. 实战中的坑与调试技巧7.1 常见 WA 原因我把自己和周围人踩过的坑汇总成表提前帮你排雷现象可能原因解决方法割点漏判根节点子节点数量统计错误确认每次 DFS 都对整棵树重新计数 childCnt桥误判为割边重边未处理存边编号用边编号跳过父边low 值整体偏低回边更新时不区分父节点判断邻边编号或是否为父节点点双分量数量不对弹出栈的终止条件写错终止条件应该是w ! v不是w ! u图不连通但只从 1 点 DFS多个连通块未处理对每个未访问点都跑一次 Tarjan递归超栈n 太大递归爆栈改迭代栈或加编译选项加大栈空间7.2 三类小题型判断做题时看到关键词建议先分类看到“必经点”“去掉哪个点图不连通”——求割点。看到“必经边”“删掉哪条边图不连通”——求桥。看到“最少加几条边变成边双连通”“边双缩点”——先求 e-DCC再缩点再看叶子数。看到“点双路径”“无法绕过的点集合”“圆方树”——求 v-DCC建圆方树。这样能少走很多弯路。7.3 调试建议实际调试时我强烈建议你先画小图不要直接在 OJ 上瞎试。比如手动画一个 5 个点的图1-2-3 组成一条链4 和 5 挂在 2 上你能肉眼看出割点是 2桥是 1-2、2-3、2-4、2-5。然后跑一遍代码把每个点的 dfn、low 打出来对比自己的手算结果哪里不对一目了然。另外我习惯在每个 if 判定旁边加注释标明这是“树边”还是“回边”后面回读代码时不用重新推。最后分享一个我自己常用的输出辅助函数在 Tarjan 结束后打印i: dfn low以及每条边(u,v) isBridge的情况。这个信息在调试时比什么调试器都好用。for (int i 1; i n; i) { cout node i : dfn dfn[i] low low[i] endl; }我个人觉得割点和桥的 Tarjan 算法本质就是“用 DFS 树上的父子关系 low 值描述绕路能力”。一旦你把 dfn 和 low 的含义吃透割点、桥、边双、点双全都能顺下来甚至连带圆方树也不会太难。写模板的时候别急着背先自己对着小图手推一个完整过程再回来看代码你会觉得这些代码简直是理所当然的。