割点与割边桥详解OI-wiki 图论连通性中的 Tarjan 算法实战指南【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 图论专题中关于**割点cut vertex与割边bridge又称桥**的完整技术指南围绕 docs/graph/cut.md 展开。割点与割边是无向图连通性分析的两大基石广泛应用于网络可靠性分析、双连通分量求解与各类 OI/ICPC 竞赛题目中。读完本文你将掌握基于 Tarjan 算法在线性时间内求解割点与割边含重边情形的完整原理、判定条件与可复现代码并能结合仓库内的例题代码与测试数据完成验证。前置概念从图论定义出发在深入算法之前先明确割点与桥在图论相关概念中的严格定义。点割集vertex cut对于连通图 $G (V, E)$若 $V\subseteq V$ 且 $G\left[V\setminus V\right]$即从 $G$ 中删去 $V$ 中的点不是连通图则 $V$ 是图 $G$ 的一个点割集。大小为一的点割集又被称作割点cut vertex。边割集edge cut若 $E\subseteq E$ 且 $G (V, E\setminus E)$ 不是连通图则 $E$ 是图 $G$ 的一个边割集。大小为一的边割集又被称作桥bridge。由此可得到两个直观的等价定义对于一个无向图如果把一个点删除后这个图的极大连通分量数增加了那么这个点就是这个图的割点又称割顶。对于一个无向图如果删掉一条边后图中的连通分量数增加了则称这条边为桥或者割边。严谨来说假设有连通图 $G{V,E}$$e$ 是其中一条边即 $e \in E$如果 $G-e$ 是不连通的则边 $e$ 是图 $G$ 的一条割边桥。割点与桥与双连通分量密切相关没有割点的连通图是点双连通的没有桥的连通图是边双连通的。理解割点与割边是进一步学习双连通分量、缩点等技巧的前提。割点定义与朴素思路的局限定义对于一个无向图如果把一个点删除后这个图的极大连通分量数增加了那么这个点就是这个图的割点。一个最朴素的想法是枚举删除每个点然后判断图的连通性。若图有 $n$ 个点、$m$ 条边删除一个点并做一次连通性判断的复杂度为 $O(nm)$整体复杂度高达 $O\big(n(nm)\big)$在竞赛数据规模下完全不可接受。因此需要引入能在 $O(nm)$ 时间内一次 DFS 解决问题的经典算法——Tarjan。割点Tarjan 算法核心原理从一张示例图出发考虑下图示例图源文件很容易看出割点是 2而且这个图仅有这一个割点删去点 2 后其余顶点被分成了左右两个互不连通的部分。两个关键数组dfn与lowTarjan 算法在 DFS 过程中维护两个核心数组dfn[u]时间戳按 DFS 访问顺序给每个点打上的时间戳。下图展示了按 DFS 序为上述示例图打上时间戳后的结果示意图源文件low[u]存储不经过其父亲能到达的最小时间戳。例如在示例图中low[2]是 1low[5]和low[6]是 3。割点的判定条件从根节点DFS 树的根开始 DFS判断某个点是否是割点的根据是对于某个顶点 $u$如果存在至少一个顶点 $v$$u$ 的儿子使得 $low_v \geq dfn_u$即 $v$ 及其子树不能回到 $u$ 的祖先那么 $u$ 点为割点。这个条件的直观含义是把 $u$ 删掉后儿子 $v$ 所在的子树将无法通过其他返祖边连接到 $u$ 以上的部分从而与图的其余部分失去联系极大连通分量数因此增加。更新low的伪代码如下$$ \begin{array}{ll} 1 \textbf{if } v \text{ is a son of } u \ 2 \qquad \text{low}_u \min(\text{low}_u, \text{low}_v) \ 3 \textbf{else} \ 4 \qquad \text{low}_u \min(\text{low}_u, \text{dfn}_v) \ \end{array} $$即对于 DFS 树中的儿子 $v$用其low值更新父亲的low对于已经访问过的非父亲邻居返祖边/横叉边用其dfn值更新当前点的low。根节点的特殊处理上述判定条件惟独不适用于搜索的起始点DFS 根节点需要特殊考虑若根节点不是割点则其他路径亦能到达全部结点因此从起始点只「向下搜了一次」即在搜索树内仅有一个子结点如果在搜索树内有两个及以上的儿子那么它一定是割点了设想示例图从 2 开始搜索搜索树内应有两个子结点3 或 4以及 5 或 6如果只有一个儿子那么把它删掉不会对连通性产生任何影响。考虑下图这种含环的情形示意图源文件我们在访问 1 的儿子时假设先 DFS 到了 2然后标记用过然后递归往下来到了 44 又来到了 3。当递归回溯的时候会发现 3 已经被访问过了可通过环回到已访问顶点所以 1 不是割点。割点模板题与完整代码解析仓库为本文档提供了配套的例题代码 docs/graph/code/cut/cut_1.cpp对应模板题洛谷 P3388【模板】割点割顶/* 洛谷 P3388 【模板】割点割顶 */ #include iostream #include vector using namespace std; int n, m; // n点数 m边数 int dfn[100001], low[100001], idx, res; // dfn记录每个点的时间戳 // low能不经过父亲到达最小的编号idx时间戳res答案数量 bool vis[100001], flag[100001]; // flag: 答案 vis标记是否重复 vectorint edge[100001]; // 存图用的 void Tarjan(int u, int fa) { // u 当前点的编号fa 自己爸爸的编号 vis[u] true; // 标记 low[u] dfn[u] idx; // 打上时间戳 int child 0; // 每一个点儿子数量 for (const auto v : edge[u]) { // 访问这个点的所有邻居 C11 if (!vis[v]) { child; // 多了一个儿子 Tarjan(v, u); // 继续 low[u] min(low[u], low[v]); // 更新能到的最小节点编号 if (fa ! u low[v] dfn[u] !flag[u]) { // 主要代码 // 如果不是自己且不通过父亲返回的最小点符合割点的要求并且没有被标记过 // 要求即为删了父亲连不上去了即为最多连到父亲 flag[u] true; res; // 记录答案 } } else if (v ! fa) { // 如果这个点不是自己的父亲更新能到的最小节点编号 low[u] min(low[u], dfn[v]); } } // 主要代码自己的话需要 2 个儿子才可以 if (fa u child 2 !flag[u]) { flag[u] true; res; // 记录答案 } } int main() { cin n m; // 读入数据 for (int i 1; i m; i) { // 注意点是从 1 开始的 int x, y; cin x y; edge[x].push_back(y); edge[y].push_back(x); } // 使用 vector 存图 for (int i 1; i n; i) // 因为 Tarjan 图不一定连通 if (!vis[i]) { idx 0; // 时间戳初始为 0 Tarjan(i, i); // 从第 i 个点开始父亲为自己 } cout res endl; for (int i 1; i n; i) if (flag[i]) cout i ; // 输出结果 return 0; }代码要点解读递归入口约定对每个连通分量从i点开始、以Tarjan(i, i)形式调用即令根节点的父亲为它自己用fa u来区分根节点见 docs/graph/code/cut/cut_1.cpp#L14-L39。非根节点判定low[v] dfn[u]说明 $v$ 的子树最多只能连回 $u$ 本身删去 $u$ 后该子树与祖先部分分离故 $u$ 是割点。根节点判定单独统计 DFS 树中的儿子数量childchild 2时根为割点。多连通分量处理主函数中循环遍历所有点对未访问的点分别启动一次 Tarjandocs/graph/code/cut/cut_1.cpp#L49-L53每次进入前将idx归零——这保证了非连通图同样适用。仓库测试数据验证仓库在 docs/graph/examples/cut/cut_1.in 提供了模板题的输入数据6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6对应的标准输出 docs/graph/examples/cut/cut_1.ans 为1 5即该 6 点 7 边的无向图中割点数量为 1唯一割点是顶点 5星形结构围绕点 5删去后图分为多个连通块。读者可以将上述代码与本组数据对照运行验证算法输出。复杂度Tarjan 算法对每个点和每条边各访问常数次时间复杂度 $O(nm)$空间复杂度 $O(n)$不含存图空间相比朴素枚举删除点的 $O\big(n(nm)\big)$ 有了质的提升。割边桥无重边情形定义和割点差不多割边又叫桥对于连通图 $G{V,E}$$e$ 是其中一条边即 $e \in E$如果 $G-e$ 是不连通的则边 $e$ 是图 $G$ 的一条割边桥。以下图中红色标注的边即为割边示意图源文件判定条件求割边的过程和割点几乎一样只要把判定条件改一处由 $low_v \geq dfn_u$ 改为$$low_v dfn_u$$即可而且不需要考虑根节点的问题。原理说明求割点时$low_v dfn_u$ 表示点 $v$ 还能通过返祖边回到父节点 $u$ 自己此时 $u$ 删掉后 $v$ 子树仍与 $u$ 相连的部分包括 $u$ 本身但 $u$ 已被删除……需要注意区分对割点$low_v dfn_u$ 时 $v$ 可以回到 $u$删去 $u$ 后 $v$ 子树与祖先部分断开但 $u$ 仍见证了这种回边因此 $u$ 是割点条件取 $\geq$对割边若 $low_v dfn_u$表示顶点 $v$ 还能回到父节点 $u$则 $u-v$ 这条边不是唯一的连接删除 $u-v$ 不影响连通性只有当 $low_v dfn_u$即 $v$ 既不能回到祖先、也没有另外一条回到父亲 $u$ 的路时$u-v$ 才是割边条件取 $$。实现无重边的无向图求割边下面代码实现了对无重边的无向图求割边。其中当isbridge[x]为真时(father[x],x)为一条割边。 Ccpp int low[MAXN], dfn[MAXN], idx; bool isbridge[MAXN]; vectorint G[MAXN]; int cnt_bridge; int father[MAXN]; void tarjan(int u, int fa) { father[u] fa; low[u] dfn[u] idx; for (const auto v : G[u]) { if (!dfn[v]) { tarjan(v, u); low[u] min(low[u], low[v]); if (low[v] dfn[u]) { isbridge[v] true; cnt_bridge; } } else if (v ! fa) { low[u] min(low[u], dfn[v]); } } } Pythonpython low [0] * MAXN dfn [0] * MAXN idx 0 isbridge [False] * MAXN G [[0 for i in range(MAXN)] for j in range(MAXN)] cnt_bridge 0 father [0] * MAXN def tarjan(u, fa): father[u] fa idx idx 1 low[u] dfn[u] idx for i in range(0, len(G[u])): v G[u][i] if dfn[v] False: tarjan(v, u) low[u] min(low[u], low[v]) if low[v] dfn[u]: isbridge[v] True cnt_bridge cnt_bridge 1 elif v ! fa: low[u] min(low[u], dfn[v]) 实现中通过father[x]数组记录每个点的父节点判定为桥时在儿子侧打标记isbridge[v] true即边(father[v], v)是桥。割边有重边时的修正然而上述无重边时的做法在有重边的无向图上是有问题的因为两节点间可能不止有一条边此时两条平行边互为替代通路删掉其中任何一条都不会影响连通性它们都不会是桥。但上述代码遇到第二条平行边时会因v fa而跳过更新错误地将low[v]判断为大于dfn[u]从而误判为桥。两种修正思路思路一将参数fa改为边编号。即把「不用父节点更新」改为「不用来时的边更新」。只要保存每条边的编号递归时传入当前边编号遇到「同一条边」时跳过更新而遇到编号不同的平行边时正常用dfn更新。这样平行边会正确地把low拉低避免误判。思路二设立一个标记判断是否已有一条边抵达父节点。这是仓库文档给出的更简单实现首次访问到父节点时置flag true但不更新再次通过另一条平行边访问到父节点时说明存在重边此时正常更新low。实现可能有重边的无向图求割边 Ccpp int low[MAXN], dfn[MAXN], idx; bool isbridge[MAXN]; vectorint G[MAXN]; int cnt_bridge; int father[MAXN]; void tarjan(int u, int fa) { bool flag false; father[u] fa; low[u] dfn[u] idx; for (const auto v : G[u]) { if (!dfn[v]) { tarjan(v, u); low[u] min(low[u], low[v]); if (low[v] dfn[u]) { isbridge[v] true; cnt_bridge; } } else { if (v ! fa || flag) low[u] min(low[u], dfn[v]); else flag true; } } } 对比两版代码可以看到有重边版本把else if (v ! fa)分支改成了else分支并在函数内新增bool flag第一次遇到父节点fa时只置标记不更新之后再次遇到说明存在另一条边连向父节点则正常更新low。这一处修改正是处理重边的关键。练习题目以下练习覆盖了割点、割边的基础判定及其在进阶问题中的综合运用洛谷 P3388【模板】割点割顶割点模板题直接套用仓库 docs/graph/code/cut/cut_1.cpp 即可通过。POJ 2117 Electricity删去一个点后最多能增加多少连通块考察对割点性质的深入理解。HDU 4738 Caocaos Bridges割边桥与边权结合的实际应用。HDU 2460 Network动态加边过程中桥的维护。POJ 1523 SPF割点移除后各连通分量的计数。延伸Tarjan 算法的更多用途Tarjan 算法是一种极具普适性的图论工具除了割点与割边它还常用于求强连通分量SCC在有向图中通过dfn/low与栈结构找出强连通分量缩点Tarjan 缩点将每个强连通分量缩成一个点把有向图转化为 DAG为后续拓扑 DP、最短路等操作提供基础2-SAT 求解基于 SCC 判定与构造 2-SAT 问题的可行解LCA 的 Tarjan 离线算法利用 DFS 与并查集在线性时间内批量回答 LCA 查询仓库 docs/graph/lca.md 有专门介绍。从源码结构看本仓库在 docs/graph/code 目录下按专题组织了大量配套代码docs/graph/examples 中为每个算法都附带了成对的.in/.ans测试数据读者可结合测试数据验证自己的实现。相关阅读双连通分量割点/割边与点双、边双连通分量的关系图论相关概念点割集、边割集、点双连通、边双连通的严格定义割点和桥相关代码目录本题配套源码割点测试数据P3388 模板题的输入输出样例【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考