1 边双
图的割边 找出了哪些边一旦删除,就会使原图分裂。现在继续划分:哪些点之间的连通关系,不会被删除一条边破坏?
一个无向连通图若没有桥,就称为边双连通的。等价地,任意两个不同顶点之间,都存在两条没有公共边的路径;这两条路径可以经过相同的中间顶点。
原图中满足这个条件的极大部分,称为边双连通分量,简称边双或 e-BCC。极大表示不能继续扩大,不是只取规模最大的部分。单个顶点也允许单独成块。
删除所有桥后,剩余的每个连通块就是一个边双。 因此每个点恰好属于一个边双,桥连接不同的边双。
2 示例
沿用割边篇的七点八边图。两个三角形由
两条桥为
用 belong[u] 记录顶点
| 顶点 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
belong[u] |
1 | 1 | 1 | 2 | 2 | 2 | 3 |
编号只是标签。两个点是否位于同一边双,取决于编号是否相等,与编号的大小无关。
3 两遍遍历
3.1 第一遍找桥
保留割边篇的 dfn、low 和边编号。对树边
就标记它为桥。
void dfs_bridge(int u, int in_edge) {
dfn[u] = low[u] = ++timer;
for (auto [v, id] : g[u]) {
if (id == in_edge) continue;
if (!dfn[v]) {
dfs_bridge(v, id);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) is_bridge[id] = true;
} else if (dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
同一条无向边在两端邻接表中共用同一个 id,只跳过进入当前点的那条边,不能跳过所有通向父亲的边,否则重边会被误判。
与前篇的区别是:现在保存 is_bridge[id],供第二遍查询,不必先把桥的端点排序输出。
3.2 第二遍编号
从一个尚未编号的点出发,忽略桥,只沿普通边遍历,把能到达的点全部标为同一编号:
void paint(int u, int color) {
belong[u] = color;
for (auto [v, id] : g[u]) {
if (is_bridge[id] || belong[v]) continue;
paint(v, color);
}
}
遍历所有起点:
for (int u = 1; u <= n; ++u) {
if (!belong[u]) paint(u, ++bcc_count);
}
第一遍的 dfn 已经非零,第二遍应使用 belong 判断是否编号,不能直接沿用第一遍的访问状态。
在样例中,从
4 正确性
先说明:一次性删除全部桥后,不会把原来的非桥变成新桥。
对于一条非桥、非自环边,两端存在另一条路径,二者组成一个环。环上的边都不是桥,所以这个绕行环在删桥后仍完整保留。自环的删除本来就不影响顶点间连通性。
因此删桥后,每个连通块内部仍不存在桥,满足边双条件。
不同块之间若原本连通,任何连接它们的路径都会经过某条原图中的桥;把两块合在一起,就不能保证删去该桥后仍连通。因此每块都已经极大。原本不连通的块当然也不能合并。
第二遍恰好求出了删桥图的全部连通块,所以得到的分量划分正确。
5 缩点森林
把每个边双缩为一个新点,把原图中的桥保留下来:
缩点时遍历每条原始无向边一次。只有桥会连接不同分量:
for (int id = 0; id < m; ++id) {
if (!is_bridge[id]) continue;
int a = belong[eu[id]], b = belong[ev[id]];
tree[a].push_back(b);
tree[b].push_back(a);
}
不能在原图的双向邻接表中不加区分地重复建边,否则同一条桥会被计算两次。完整模板同时维护缩点后的 degree。
5.1 为什么是森林
若缩点后存在环,环上的一条桥就能通过环的其余部分绕行;每个分量内部也连通,所以原图中同样存在绕行路径,与它是桥矛盾。
缩点不会改变原图的连通分量数。因此:
- 原图连通,缩点后是一棵桥树。
- 原图不连通,缩点后是一片森林。
- 孤立顶点缩成的点,度数为
。
设原图有
样例中
6 容易混淆
6.1 边双内部可以有割点
两个三角形共用一个顶点
边双关心删边,点双关心删点。不同边双不共用顶点;割点却可能属于多个点双。 不能把割点当成划分边双的边界。
点双的边栈分块方法见 点双连通分量。
6.2 low 不是分量编号
在上图中,按
虽然 low 不全相等,五个点仍属于同一个边双。树边
low 用于判定边是否为桥,belong 才表示分量。不要直接把 low 相等的点分为一组。
7 代码
采用 luogu P8436: 【模板】边双连通分量 的格式:输入
输出第一行为分量数;随后每行先输出该分量的点数,再输出成员。原题允许任意顺序,模板按最小未编号顶点依次编号,再按原顶点顺序收集成员,便于手算核对。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
const int maxm = 2000000 + 5;
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
vector<int> block[maxn], tree[maxn];
int eu[maxm], ev[maxm]; // 每条原始无向边只记录一份端点
int dfn[maxn], low[maxn], belong[maxn], degree[maxn];
bool is_bridge[maxm];
int timer = 0, bcc_count = 0, connected_count = 0;
// 第一遍:只标记桥,按边号跳过进入当前点的边。
void dfs_bridge(int u, int in_edge) {
dfn[u] = low[u] = ++timer;
for (auto [v, id] : g[u]) {
if (id == in_edge) continue;
if (!dfn[v]) {
dfs_bridge(v, id);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) is_bridge[id] = true;
} else if (dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
// 第二遍:忽略所有桥,把能够到达的点标为同一分量。
void paint(int u, int color) {
belong[u] = color;
for (auto [v, id] : g[u]) {
if (is_bridge[id] || belong[v]) continue;
paint(v, color);
}
}
void build_components(int n) {
for (int u = 1; u <= n; ++u) {
if (dfn[u]) continue;
++connected_count;
dfs_bridge(u, -1);
}
for (int u = 1; u <= n; ++u) {
if (!belong[u]) paint(u, ++bcc_count);
}
// 按原编号收集成员,使每个分量内的输出顺序固定。
for (int u = 1; u <= n; ++u) block[belong[u]].push_back(u);
}
void build_forest(int m) {
for (int id = 0; id < m; ++id) {
if (!is_bridge[id]) continue;
int a = belong[eu[id]], b = belong[ev[id]];
tree[a].push_back(b);
tree[b].push_back(a);
++degree[a];
++degree[b];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
cin >> eu[id] >> ev[id];
g[eu[id]].push_back({ev[id], id});
g[ev[id]].push_back({eu[id], id});
}
build_components(n);
build_forest(m); // 保存桥树/森林,不额外输出,供后续应用使用
cout << bcc_count << '\n';
for (int color = 1; color <= bcc_count; ++color) {
cout << block[color].size();
for (int u : block[color]) cout << ' ' << u;
cout << '\n';
}
return 0;
}
代码保留了两个结果:
block[c]:第个边双的全部顶点。 tree[c]、degree[c]:缩点森林中与第个边双相邻的分量及其度数。
森林只保存在内存中,不增加输出,避免改变模板题的输出格式。
7.1 示例输入
7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7
输出:
3
3 1 2 3
3 4 5 6
1 7
两条桥的代码边号分别为
7.2 非递归版本
递归版两遍遍历的深度都可能达到
第一遍必须保留 DFS 的“进入、处理下一条边、退出回传”顺序。只有孩子处理完,才能把它的 low 回传给父亲;不能简单改成普通 BFS。第二遍只是求连通块,使用普通栈即可。
非递归完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
const int maxm = 2000000 + 5;
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
vector<int> block[maxn], tree[maxn];
int eu[maxm], ev[maxm]; // 每条原始无向边只记录一份端点
int dfn[maxn], low[maxn], belong[maxn], degree[maxn];
bool is_bridge[maxm];
int timer = 0, bcc_count = 0, connected_count = 0;
int parent[maxn], parent_edge[maxn], next_edge[maxn], stk[maxn];
// 第一遍:显式模拟递归 DFS,退出孩子时才向父亲回传 low。
void dfs_bridge(int root, int in_edge) {
int top = 0;
parent[root] = 0;
parent_edge[root] = in_edge;
next_edge[root] = 0;
dfn[root] = low[root] = ++timer;
stk[top++] = root;
while (top) {
int u = stk[top - 1];
if (next_edge[u] == (int)g[u].size()) {
--top; // u 的全部邻边处理完,对应递归返回
int p = parent[u];
if (p != 0) {
low[p] = min(low[p], low[u]);
if (low[u] > dfn[p]) is_bridge[parent_edge[u]] = true;
}
continue;
}
auto [v, id] = g[u][next_edge[u]++];
if (id == parent_edge[u]) continue;
if (!dfn[v]) {
parent[v] = u;
parent_edge[v] = id;
next_edge[v] = 0;
dfn[v] = low[v] = ++timer;
stk[top++] = v;
} else if (dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
// 第二遍:普通栈遍历,入栈时立即标记,每个点只入栈一次。
void paint(int start, int color) {
int top = 0;
belong[start] = color;
stk[top++] = start;
while (top) {
int u = stk[--top];
for (auto [v, id] : g[u]) {
if (is_bridge[id] || belong[v]) continue;
belong[v] = color;
stk[top++] = v;
}
}
}
void build_components(int n) {
for (int u = 1; u <= n; ++u) {
if (dfn[u]) continue;
++connected_count;
dfs_bridge(u, -1);
}
for (int u = 1; u <= n; ++u) {
if (!belong[u]) paint(u, ++bcc_count);
}
// 按原编号收集成员,使每个分量内的输出顺序固定。
for (int u = 1; u <= n; ++u) block[belong[u]].push_back(u);
}
void build_forest(int m) {
for (int id = 0; id < m; ++id) {
if (!is_bridge[id]) continue;
int a = belong[eu[id]], b = belong[ev[id]];
tree[a].push_back(b);
tree[b].push_back(a);
++degree[a];
++degree[b];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
cin >> eu[id] >> ev[id];
g[eu[id]].push_back({ev[id], id});
g[ev[id]].push_back({eu[id], id});
}
build_components(n);
build_forest(m); // 保存桥树/森林,不额外输出,供后续应用使用
cout << bcc_count << '\n';
for (int color = 1; color <= bcc_count; ++color) {
cout << block[color].size();
for (int u : block[color]) cout << ' ' << u;
cout << '\n';
}
return 0;
}
第一遍的 stk 保存当前 DFS 路径,next_edge[u] 记录该点处理到了哪条邻边。第二遍复用这个栈,但入栈时立即设置 belong,保证每个点只入栈一次。
两版使用同样的边编号、分量编号与输出方式,只是遍历的实现不同。
8 应用
8.1 必经桥数量
原图中查询
若两点原本连通,桥树上
因此结合 爬树法求 LCA(倍增),可以求
样例中
8.2 加边消桥
若原图连通,且允许新边与已有边连接相同的一对顶点,可以在桥树上分析最少加几条边,使整张图不再有桥。
若只剩一个缩点,原图已经边双,答案为
下界:每个叶子对应的部分仅通过一条桥与外界相连,至少需要一条新边连向外界。一条新边最多照顾两个叶子,因此至少需要
上界:可以按 DFS 叶子顺序跨两半配对,使新边形成的环覆盖全部树边。下面四个叶子的例子,只需连接
不能只随意把叶子两两配对。例如只连接左侧的
配对上界的说明
对于至少三个点的树,选一个非叶点作根,按 DFS 顺序列出所有叶子。叶子数为奇数时,将最后一个叶子再列一次,得到长度为
将第
对任意树边,删去后,孩子一侧的叶子在 DFS 序列中构成一个非空的连续区间,其余叶子也非空。一个非空且不占满整圈的连续区间,不可能在“下标平移半圈”后保持不变,因此至少有一对配对叶子分处两侧。
这对新边与原树路径构成环,覆盖被考察的树边。每条树边都如此,所以全部原桥都被消除;新边自身也位于对应的环上。
只有两个缩点时,添加一条与原桥平行的边即可。缩点代表一整块顶点时,从对应两块中各选任意一个真实顶点作为新边端点。
这个结论使图变成边双,不保证变成点双。原图不连通时,不能直接对整片森林数叶子套同一公式。
9 复杂度与边界
找桥、忽略桥编号、收集成员、建立缩点森林,都只扫描每个点或每条边常数次,总时间为
- 模板容量为
、 ,每条无向边有两条邻接表记录,但桥标记只开 份。 - 两条重边可以互相绕行,都不是桥;必须按边编号过滤进入边。
- 自环不会成为桥,也不会把顶点接到另一个分量。
- 孤立点单独成块;即使没有边,也应处理所有顶点。
- 没有桥不代表整张图只有一个边双,原图可能有多个互不连通的无桥分量。
- 多组数据要清空邻接表、成员表、缩点森林及所有状态数组,重置计时器与分量计数。
10 练习
10.1 手算
- 两个点之间有两条平行边,再加一个孤立点。边双数、桥数、原连通分量数分别是多少?
- 三角形
接一条边 ,再加孤立点 。三个边双是什么? - 两个三角形只共用一个顶点,是否会因为有割点而拆成两个边双?
参考结果
- 分别为
。平行边的两个端点属于同一边双,孤立点另成一块。 、 、 。有 ,满足 。 - 不会。没有桥,整张图仍是一个边双。
10.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 模板 | luogu P8436: 【模板】边双连通分量 | 输出全部边双,处理重边、自环与大规模深链。 |
| 加边应用 | luogu P2860: [USACO06JAN] Redundant Paths G | 原图连通且允许添加平行道路,缩点后统计叶子,求最少加边数。 |
| 缩点路径 | codeforces 1000E | 将两点间必经桥数转为桥树距离,再求桥树直径;可结合 树的直径 学习。 |
11 相关题解
暂无相关题解