本课时有配套视频讲解，购买后即可观看（永久有效）
割边
一、课上练习
编程练习
- 割边：L49995
二、知识总结
✨ 核心思想
割边（Bridge），也称为桥，是无向连通图中的一条边：删除该边后，图的连通分量数增加。换言之，桥是图中"不可替代"的连接通道。
割边的求解同样基于 Tarjan 的 DFS 框架，核心判定条件与割点类似但更为严格：对于树边 (u, v)，如果 low[v] > dfn[u]（注意是严格大于），则该边是桥。
✨ 算法原理
割边 vs 割点的判定差异
| 概念 | 判定条件 | 含义 |
|---|---|---|
| 割点 | low[v] >= dfn[u] | v 的子树不能到达 u 或 u 的祖先 |
| 割边 | low[v] > dfn[u] | v 的子树不能到达 u（连 u 本身都到不了） |
割边条件更严格的原因：如果 low[v] == dfn[u]，说明 v 的子树有返祖边连到 u，删除边 (u,v) 后仍可通过该返祖边绕回，所以 (u,v) 不是桥。
重边的处理
在有重边的图中，两个节点之间如果有多条边，则这些边都不是桥（删除其中一条，还有另一条可以连通）。因此必须正确处理重边，通常的做法是使用边的编号而非父节点编号来判断。
链式前向星与边编号
为了正确处理重边，我们使用链式前向星存图，将每条无向边存为编号 2i 和 2i+1 的一对有向边。通过异或操作 i ^ 1 可以快速找到反向边。
✨ 代码实现
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const int MAXM = 200005; // 边数上限（无向边×2）
6
7// 链式前向星存图
8struct Edge {
9 int to, next;
10} edges[MAXM * 2];
11int head[MAXN], edge_cnt = 0;
12
13int dfn[MAXN], low[MAXN];
14int timer_cnt = 0;
15int n, m;
16vector<pair<int,int>> bridges; // 存储所有桥
17
18// 加边（成对存储，编号从0开始）
19void add_edge(int u, int v) {
20 edges[edge_cnt] = {v, head[u]};
21 head[u] = edge_cnt++;
22 edges[edge_cnt] = {u, head[v]};
23 head[v] = edge_cnt++;
24}
25
26// Tarjan 求桥
27// from_edge: 到达 u 的那条边的编号，用于排除反向边
28void tarjan(int u, int from_edge) {
29 dfn[u] = low[u] = ++timer_cnt;
30
31 for (int i = head[u]; i != -1; i = edges[i].next) {
32 int v = edges[i].to;
33 if (!dfn[v]) {
34 // 树边
35 tarjan(v, i);
36 low[u] = min(low[u], low[v]);
37
38 // 桥的判定：严格大于
39 if (low[v] > dfn[u]) {
40 bridges.push_back({u, v});
41 }
42 } else if (i != (from_edge ^ 1)) {
43 // 返祖边，且不是来时的反向边
44 // 用异或排除反向边，正确处理重边
45 low[u] = min(low[u], dfn[v]);
46 }
47 }
48}
49
50int main() {
51 ios::sync_with_stdio(false);
52 cin.tie(nullptr);
53
54 memset(head, -1, sizeof(head));
55
56 cin >> n >> m;
57 for (int i = 0; i < m; i++) {
58 int u, v;
59 cin >> u >> v;
60 add_edge(u, v);
61 }
62
63 // 处理所有连通分量
64 for (int i = 1; i <= n; i++) {
65 if (!dfn[i]) {
66 tarjan(i, -1);
67 }
68 }
69
70 // 输出所有桥
71 cout << bridges.size() << "\n";
72 for (auto [u, v] : bridges) {
73 cout << u << " " << v << "\n";
74 }
75
76 return 0;
77}✨ 执行示例
以下图为例（5 个节点，5 条边）：
边：1-2, 1-3, 2-3, 3-4, 4-5
DFS 从节点 1 开始（边编号从 0 开始）：
| 步骤 | 节点 | dfn | low | 操作 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 访问 1 |
| 2 | 2 | 2 | 2 | 树边 1→2 |
| 3 | 3 | 3 | 1 | 树边 2→3，返祖边 3→1，low[3]=1 |
| 回溯 | 2 | 2 | 1 | low[2] = min(2, low[3]) = 1 |
| 4 | 4 | 4 | 4 | 树边 3→4 |
| 5 | 5 | 5 | 5 | 树边 4→5 |
回溯检查桥：
- 边 (4,5)：low[5]=5 > dfn[4]=4 → 是桥
- 边 (3,4)：low[4]=4 > dfn[3]=3 → 是桥
- 边 (2,3)：low[3]=1 > dfn[2]=2 → 不成立，不是桥
- 边 (1,2)：low[2]=1 > dfn[1]=1 → 不成立，不是桥
结果：桥为 {(3,4), (4,5)}
✨ 解题步骤详解
- 建图：使用链式前向星存边，边编号从 0 开始，成对存储。
- 初始化：
head数组初始化为 -1，dfn数组清零。 - DFS 求桥：
- 记录时间戳
dfn[u] = low[u] = ++timer_cnt。 - 遍历所有出边，通过
i != (from_edge ^ 1)排除反向边。 - 树边递归后检查
low[v] > dfn[u]判断是否为桥。
- 记录时间戳
- 收集结果：输出所有被标记为桥的边。
✨ 常见错误
- 判定条件写成 >= 而非 >：割边的条件是
low[v] > dfn[u]（严格大于），写成>=会多找出一些不是桥的边。 - 用父节点而非边编号排除反向边：当存在重边时，
v != fa的写法会把所有连向父节点的边都排除，导致重边被误判为桥。必须用边编号的异或技巧。 - 边编号没有从 0 开始：异或技巧要求一对边的编号分别为
2i和2i+1，如果从 1 开始编号则异或结果不对。 - 忘记初始化 head 为 -1：链式前向星中 head 值 -1 表示链表结尾，忘记初始化会导致遍历异常。
- 混淆有向图和无向图：桥的概念仅适用于无向图。有向图中的类似概念是强连通分量。
✨ 算法评价
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(V + E) |
| 空间复杂度 | O(V + E) |
| 适用场景 | 网络中关键链路识别、边双连通分量缩点的前置步骤 |
| 优势 | 线性时间，能正确处理重边 |
| 局限 | 仅适用于无向图 |
桥的概念在实际应用中十分重要：在通信网络中，桥代表着单点故障链路；在算法竞赛中，缩掉所有桥后得到的边双连通分量是许多高级图论问题的基础。
三、课后练习
编程练习
- 炸铁路：L49982