企业官网建设流程全解析

割点与割边（桥）详解：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(n+m)$，整体复杂度高达 $O\big(n(n+m)\big)$，在竞赛数据规模下完全不可接受。因此需要引入能在 $O(n+m)$ 时间内一次 DFS 解决问题的经典算法——Tarjan。

割点：Tarjan 算法核心原理

从一张示例图出发

考虑下图（示例图源文件）：

很容易看出割点是 2，而且这个图仅有这一个割点：删去点 2 后，其余顶点被分成了左右两个互不连通的部分。

两个关键数组：dfn与low

Tarjan 算法在 DFS 过程中维护两个核心数组：

1. dfn[u]（时间戳）：按 DFS 访问顺序给每个点打上的时间戳。下图展示了按 DFS 序为上述示例图打上时间戳后的结果（示意图源文件）：

2. low[u]：存储不经过其父亲能到达的最小时间戳。

例如在示例图中，low[2]是 1，low[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，然后标记用过，然后递归往下，来到了 4，4 又来到了 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：标记是否重复 vector<int> 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]) { // 访问这个点的所有邻居 （C++11） 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 树中的儿子数量child，child >= 2时根为割点。
• 多连通分量处理：主函数中循环遍历所有点，对未访问的点分别启动一次 Tarjan（docs/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(n+m)$，空间复杂度 $O(n)$（不含存图空间），相比朴素枚举删除点的 $O\big(n(n+m)\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)为一条割边。

=== "C++"

```cpp int low[MAXN], dfn[MAXN], idx; bool isbridge[MAXN]; vector<int> 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]); } } } ```

=== "Python"

```python 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。

实现：可能有重边的无向图求割边

=== "C++"

```cpp int low[MAXN], dfn[MAXN], idx; bool isbridge[MAXN]; vector<int> 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 Caocao's 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