OI-wiki 图论专题无向图双连通分量边双 / 点双的 Tarjan 与差分算法全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读双连通分量是图论与 OI/ICPC 竞赛中的核心概念之一它刻画了无向图在删除单条边或单个点后仍能保持连通性的冗余结构。本文以 OI-wiki 的 双连通分量文档 为主体结合仓库内 bcc 目录 的四份可直接运行的 C 实现与 配套测试数据系统讲解边双连通分量E-BCC与点双连通分量V-BCC的定义、DFS 生成树性质以及三种主流求解思路两种 Tarjan 算法和基于树上差分的算法。读完后你将掌握判定桥、割点与双连通分量的完整理论并能对照源码写出可提交的模板代码。阅读本文前建议先了解 图论相关概念并配合阅读 割点和桥 与 强连通分量 章节。基本定义边双连通与点双连通在一张连通的无向图中对于两个点 $u$ 和 $v$如果无论删去哪一条边只能删一条都不能使 $u,v$ 不连通称 $u$ 和 $v$边双连通如果无论删去哪一个点只能删一个且不能删 $u$、$v$ 自己都不能使 $u,v$ 不连通称 $u$ 和 $v$点双连通。割点与桥的更严谨定义参见 图论相关概念 与 割点和桥。两个值得注意的性质边双连通具有传递性若 $x,y$ 边双连通$y,z$ 边双连通则 $x,z$ 也边双连通。因此边双连通关系是等价关系可以直接用来划分连通块。点双连通不具有传递性下图中 $A,B$ 点双连通$B,C$ 点双连通但 $A,C$ 并不点双连通——因为删除 $B$ 后 $A$ 与 $C$ 即被分开。基于上述定义无向图中的极大边双连通子图称为边双连通分量Edge-Biconnected Component无向图中的极大点双连通子图称为点双连通分量Vertex-Biconnected Component也叫块Block。DFS 生成树分析无向图连通性的基本工具对于一张连通的无向图从任意一点开始 DFS 可以得到原图的一棵 DFS 生成树以起点为根。生成树上的边称为树边不在生成树上的边称为非树边。由于 DFS 的访问顺序栈式遍历性质可以保证所有非树边连接的两个点在生成树上满足其中一个是另一个的祖先。这一性质是后续所有算法的基石——非树边只会从祖先指向后代因此每一条非树边都唯一对应树上的一条由树边构成的简单路径。最朴素的 DFS 遍历框架如下void DFS(int p) { visited[p] true; for (int to : edge[p]) if (!visited[to]) DFS(to); }def DFS(p): visited[p] True for to in edge[p]: if visited[to] False: DFS(to)边双连通分量E-BCC以洛谷 P8436【模板】边双连通分量为例给定 $n$ 个节点、$m$ 条无向边的图需要输出边双连通分量的个数以及每个分量内的顶点集合。下面给出三种求解方法时间复杂度均为 $O(nm)$。Tarjan 算法 1先求桥再 DFS 划分思路分为两步用 Tarjan 求出图中所有桥求桥的方法见 割点和桥 的桥部分删掉所有桥之后图中剩下的每个连通块就是一个边双连通分量再 DFS 一遍即可划分。判定桥的核心条件是 $low_v dfn_u$对于树边 $u\to v$这与求割点的条件 $low_v \ge dfn_u$ 恰好差一个等号当 $v$ 无法通过非树边回到 $u$ 或更早的祖先时$u-v$ 这条边就是桥。仓库中的 bcc_1.cpp 是本题的完整实现。关键点如下使用链式前向星存无向边tot从 1 开始这样边i的反向边恒为i ^ 1便于在 DFS 中跳过来时的边i ! (in ^ 1)从而正确处理重边tarjan中当dfn[x] low[v]时把bz[i]与bz[i ^ 1]同时标记为桥第二遍dfs从每个未被分组的点出发遇到桥边bz[i]为真就停止扩展从而把分量完整切分出来。void tarjan(int x, int in) { dfn[x] low[x] bcc_cnt; for (int i hd[x]; i; i e[i].nt) { int v e[i].to; if (dfn[v] 0) { tarjan(v, i); if (dfn[x] low[v]) bz[i] bz[i ^ 1] true; // (x,v) 是桥 low[x] min(low[x], low[v]); } else if (i ! (in ^ 1)) low[x] min(low[x], dfn[v]); } } void dfs(int x, int id) { vis_bcc[x] id, bcc[id - 1].push_back(x); for (int i hd[x]; i; i e[i].nt) { int v e[i].to; if (vis_bcc[v] || bz[i]) continue; // 桥边不能跨过 dfs(v, id); } }主函数中对每个未访问点调用tarjan(i, 0)即可处理不连通图输出时先打印分量个数再逐行输出每个分量的大小与顶点编号。仓库中 bcc_1.in 与 bcc_1.ans 提供了可验证的样例5 点 8 边的图含重边与自环应输出 1 个包含全部 5 个点的边双连通分量。Tarjan 算法 2类比强连通分量无向图中 DFS 生成树上的边不是树边就是非树边这给了我们一个更简洁的思路在无向图中只要一个分量没有桥那么在 DFS 生成树上它的所有点都在同一个强连通分量中反过来DFS 生成树上的一个强连通分量在原无向图中就是边双连通分量。因此求边双连通分量的过程实际上就是在无向图上跑一遍求强连通分量的 Tarjan。仓库中的 bcc_2.cpp 正是这个思路维护一个栈st当dfn[u] low[u]时把栈顶到 $u$ 的部分弹出一个分量。与有向图版本唯一的区别是用来时的边编号i (in ^ 1)跳过代替父节点判断从而保证无向边不被反向边干扰。void tarjan(int u, int in) { low[u] dfn[u] bcc_cnt; st.push(u), vis[u] true; for (int i hd[u]; i; i e[i].nt) { int v e[i].to; if (i (in ^ 1)) continue; if (!dfn[v]) tarjan(v, i), low[u] min(low[u], low[v]); else if (vis[v]) low[u] min(low[u], dfn[v]); } if (dfn[u] low[u]) { // 弹出强连通分量即原图的边双连通分量 vectorint t; t.push_back(u); while (st.top() ! u) t.push_back(st.top()), vis[st.top()] false, st.pop(); st.pop(), ans.push_back(t); } }这一算法的正确性依赖于无桥分量内任意两点可互相到达这一事实从源码结构看它省去了显式求桥与二次 DFS实现更紧凑。差分算法非树边覆盖与树上差分先看一张示意图图中黑色与绿色边为树边红色边为非树边。每条非树边的两个端点唯一对应树上一条由树边构成的简单路径称这条非树边覆盖了该路径上的所有边。具体来说绿色的树边至少被一条非树边覆盖黑色的树边不被任何非树边覆盖。于是得到关键结论非树边与被至少一条非树边覆盖的树边一定不是桥未被任何非树边覆盖的树边一定是桥。暴力的做法是枚举每条非树边、逐条把覆盖的树边标记为绿复杂度 $O(nm)$。优化方式是用树上差分对每条非树边在其树上深度较大的端点打1标记深度较小的端点打-1标记$O(n)$ 求出每个点子树内部的标记和对点 $u$子树标记和等于覆盖 $u$ 与 $fa_u$ 之间树边的非树边数量若该值为 $0$则 $u$ 与 $fa_u$ 之间的树边是桥最后再 DFS 一遍不跨过桥边即得边双连通分量。仓库中的 bcc_4.cpp 给出了完整实现其中有两个值得注意的工程细节用vector实现简易哈希表re判重边、be记桥键为min(x,y) * N max(x,y)的哈希编码因为题目时空限制较紧源码注释里也给出了不紧时可用的mappairint,int, int替代方案dfs先算深度与差分值dfs2自底向上累加子树和并判定桥dfs3沿非桥边划分分量。int dep[N], bz[N], sum[N]; // 深度、单点差分值、子树差分和 void dfs(int x, int pre) { // 计算深度与单点差分 if (dep[x] dep[pre]) bz[x], bz[pre]--; // 回到祖先更新差分 if (dep[x]) return; dep[x] dep[pre] 1; for (int i hd[x]; i; i e[i].nt) dfs(e[i].to, x); } int dfs2(int x, int pre) { // 处理子树差分和sum[x] 0 即 (x,pre) 是桥 if (vis[x] 1) return sum[x]; vis[x] 1, sum[x] bz[x]; for (int i hd[x]; i; i e[i].nt) { int v e[i].to; if (dep[v] dep[x] !vis[v]) sum[x] dfs2(v, x); } if (sum[x] 0 re[P(x, pre)] 1) be[P(x, pre)] 1; return sum[x]; }扩展应用CEOI2015 Day1「管道」——16MB 内存下的求桥问题本题要求对一张 $N$ 点 $M$ 边、不保证连通的无向图求每个连通块视为子图中的所有桥但内存只有 16 MB。题解的关键观察是既然存不下所有边就考虑优化存边——若一条非树边被另一条非树边完全覆盖则这条边是无用的去掉它不影响桥的判定。可以用并查集维护将所有非树边按对应路径长度从短到长处理用并查集把已被覆盖的树边跳过从而只保留必要的边信息在极低内存下完成求桥。这展示了差分思想在空间受限场景下的变体应用。点双连通分量V-BCC以洛谷 P8435【模板】点双连通分量为例输出点双连通分量的个数以及每个分量。需要先学习割点的判定参见 割点和桥 的割点部分。Tarjan 算法点双连通分量的 Tarjan 算法基于以下两条性质两个点双最多只有一个公共点且该公共点一定是割点——这正是点双之间通过割点串联的结构对于一个点双它在 DFS 搜索树中 $dfn$ 值最小的点一定是割点或者树根。根据性质 2 分类讨论当这个点是割点时它一定是所在点双连通分量的根因为一旦包含它的父节点它仍然是割点分量就无法再极大了当这个点是树根时有两个及以上子树则它是割点只有一个子树则它是该子树的一个点双连通分量的根没有子树孤立点视作一个单独的点双。仓库中的 bcc_3.cpp 是完整实现。核心流程DFS 过程中维护栈sta当发现low[v] dfn[u]$v$ 是 $u$ 的儿子且不能绕回 $u$ 上方时说明 $u$ 是一个割点候选此时从栈顶弹出直到弹出 $v$再压入 $u$即构成一个点双同时用f 1 || u ! root判定 $u$ 是否为割点。对孤立点u root hd[u] 0直接单独形成一个分量。void tarjan(int u) { dfn[u] low[u] bcc_cnt, sta[top] u; if (u root hd[u] 0) { // 孤立点单独一个点双 dcc[cnt].push_back(u); return; } int f 0; for (int i hd[u]; i; i e[i].nt) { int v e[i].to; if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); if (low[v] dfn[u]) { // u 是 v 所在点双的底部割点 if (f 1 || u ! root) cut[u] true; cnt; do dcc[cnt].push_back(sta[top--]); while (sta[top 1] ! v); dcc[cnt].push_back(u); // 割点本身同时属于相邻的多个点双 } } else low[u] min(low[u], dfn[v]); } }注意与边双不同割点会被同时计入它所属的多个点双连通分量这正是两个点双至多共享一个割点性质的直接体现。差分算法蓝点图点双同样有基于差分的做法。如上图黑色边为树边红色边为非树边每条非树边对应树上一条由树边构成的简单路径。构造一张新图新图中的每个点对应原图中的每一条树边图中用蓝色点表示对原图中的每条非树边把它对应路径上的所有树边在新图中对应的蓝点连成一个连通块图中用蓝色边体现。在这个新图模型下成立如下判定一个点不是割点当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块两个点点双连通当且仅当它们在原图树上的路径中的所有边在新图中对应的蓝点都属于同一个连通块——即图中的每个蓝点连通块都对应一个点双连通分量。蓝点间的连通关系可以用与求边双时相同的差分技巧维护路径覆盖 子树求和整体时间复杂度 $O(nm)$。其思想本质是把点的连通性问题转化为边蓝点的连通性问题从而复用差分的高效性。算法对比与选型建议算法求解对象核心思想实现要点仓库源码Tarjan 算法 1边双先求桥删桥后 DFS 划分链式前向星i^1处理反向边与重边bcc_1.cppTarjan 算法 2边双无向图强连通分量即边双栈 dfnlow弹栈bcc_2.cpp差分算法边双非树边覆盖 树上差分判桥子树差分和、哈希判重边bcc_4.cppTarjan 算法点双割点性质 栈式划分割点同时归属多个分量bcc_3.cpp差分算法点双边转点蓝点连通块差分维护路径覆盖理论见本文实际竞赛中只需判桥/求边双且图较大时Tarjan 算法 1 或 2 最直接Tarjan 算法 2 代码更短需要边双内部的边集或对桥做进一步缩点处理时算法 1 的桥标记天然可用内存受限或需要对路径覆盖做批量处理时差分算法bcc_4.cpp 的思路更优CEOI2015「管道」即典型场景求点双块并处理割点时必须用点双专属的 Tarjan 实现bcc_3.cpp注意割点会出现在多个分量中。四份代码均配套有 输入输出样例例如 bcc_1.in 构造了含重边2 4与自环1 1的 5 点图bcc_1.ans 验证了其边双分量应为全部 5 个点——重边与自环都不影响边双连通性可直接用于自测你的实现。小结边双连通具有传递性、可按等价类划分点双连通不具传递性分量之间以割点衔接DFS 生成树保证非树边两端是祖先-后代关系这是所有 $O(nm)$ 算法的共同前提边双连通分量可用先求桥再划分或直接类比强连通分量两种 Tarjan 求解也可用非树边覆盖 树上差分求解点双连通分量的 Tarjan 依赖割点性质割点会同时属于多个分量差分思想在两种分量上均可推广且在空间受限16MB 内存场景下仍是关键优化手段。若要继续深入可阅读仓库中相关的 图论概念、割点和桥、强连通分量 以及块-割点树Block-Cut Tree等进阶内容。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考