1 割边
在无向图中,删除一条边后,若图的连通分量数增加,则称这条边为割边,也称桥(bridge)。删除边时保留它的两个端点。
若删除边
枚举删除每条边,再用 DFS 或 BFS 统计连通分量,时间复杂度为
本文沿用 图的割点 中的 DFS 树、树边与回边概念。
2 判定条件
2.1 dfn 与 low
:第一次访问点 的次序。 :从 出发,沿树边向下走若干步,再走至多一条回边,能到达的点中最小的 DFS 序。允许不走任何边。
初值为
| 边的类型 | 更新方式 |
|---|---|
| 树边 |
|
| 回边 |
进入当前点的那条无向边必须跳过,否则会把沿原路返回父亲误当作另一条路。
2.2 树边判定
设
如果
树边
非树边不可能是割边:它的两端已经由 DFS 树上的路径连接,删除它不影响连通性。根节点发出的树边也使用同一判定,无须特殊处理。
2.3 等号的区别
割点与割边的判定相差一个等号。
| 判定对象 | 条件 | 删除后需要绕过什么 |
|---|---|---|
| 非根点 |
存在孩子 |
整个点 |
| 树边 |
这一条边,点 |
当
两种概念也不能仅凭端点互相推断。例如,只有两个点、一条边的图中,这条边是割边,但两个端点都不是割点。反过来,两条环共用的点是割点,图中却可以没有割边。
3 示例
下面指定 DFS 顺序为
| 点 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 1 | 1 | 4 | 4 | 4 | 7 |
- 对树边
,有 ,所以它是割边。 - 对树边
,有 ,所以它是割边。 - 对树边
,有 ,可经 绕行,所以它不是割边。
4 重边处理
旧模板使用 if (v == parent) continue 跳过父亲。简单图中可以这样写,但有重边时会出错。
假设
若把所有通向父亲的边都跳过,就会漏掉这条回边,错误地判出割边。
因此,每条无向边分配一个唯一编号,两端邻接表中的记录共用该编号。递归时传入边号,只跳过进入当前点的那一条边。自环也不是割边,代码中不会将它作为树边。
5 代码实现
输入
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5; // 按题目点数上限设置
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
int dfn[maxn], low[maxn];
vector<pair<int, int>> bridges;
int timer = 0;
void dfs(int u, int in_edge) {
dfn[u] = low[u] = ++timer;
for (auto [v, id] : g[u]) {
if (id == in_edge) continue; // 只跳过进入 u 的那条边
if (!dfn[v]) {
dfs(v, id);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
bridges.push_back({min(u, v), max(u, v)});
}
} else if (dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
int u, v;
cin >> u >> v;
g[u].push_back({v, id});
g[v].push_back({u, id});
}
for (int u = 1; u <= n; ++u) {
if (!dfn[u]) dfs(u, -1);
}
sort(bridges.begin(), bridges.end());
for (auto [u, v] : bridges) {
cout << u << ' ' << v << '\n';
}
return 0;
}
外层循环从每个未访问的点开始 DFS,处理所有连通分量。割边只在树边递归返回后记录,每条边至多记录一次。
Tarjan 部分的时间复杂度为
5.1 示例输入
下面的边顺序会得到前文指定的 DFS 顺序。
7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
输出:
3 4
6 7
6 环与缩点
一条边是割边,当且仅当它不属于任何环。
若它在环上,删边后还能沿环的另一侧连接两端,因此不是割边。反之,若删边后两端仍有另一条路径,加回这条边就组成了一个环。重边形成的两条边也提供了彼此的绕行路径。
删除所有割边后,剩余的连通块称为边双连通分量,孤立点也单独成块。将每块缩成一个点,原来的割边连接这些新点,得到一片森林;原图连通时是一棵树。若缩点后仍有环,环上的边就有绕行路径,与它们是割边矛盾。
7 练习
| 题目 | 练习重点 |
|---|---|
| [[[p: atcoder-abc075_c | ABC075 C Bridge]]] |
| [[[p: luogu-P1656 | P1656 炸铁路]]] |
8 相关题解
暂无相关题解