边双连通分量(Tarjan 求桥 + 删桥染色)
无向图求桥(low[v] > dfn[u])后删桥 DFS 染色求边双连通分量,O(n+m);含数组逐项解释、输出桥的两种写法、易错/易混清单与交互动画
定义:删掉一条边后图不再连通,这条边就是桥;图中不含桥的极大连通块称为边双连通分量(EBCC)。 等价说法:分量内任意两点之间存在两条边不相交的路径。
求法两步:Tarjan 求桥 → 删掉所有桥后 DFS 染色,复杂度 O(n + m)。
代码(洛谷 P8436 已 AC)
#include <bits/stdc++.h>
using namespace std;
const int N = (int)5e5 + 5;
const int M = (int)2e6 + 5;
struct edge{
int to,ne;
}e[M<<1];
int n,m;
int he[N],tot=1;
void add(int u,int v){
e[++tot].to=v;
e[tot].ne=he[u];
he[u]=tot;
}
int b[M<<1];
int dfn[N],low[N],timer;
int vis[N];
vector<vector<int>> ans;
void tarjan(int u,int f){
dfn[u]=low[u]=++timer;
for(int i=he[u];i;i=e[i].ne){
int v=e[i].to;
if(!dfn[v]){
tarjan(v,i);
if(low[v]>dfn[u]) b[i]=b[i^1]=true;
low[u]=min(low[u],low[v]);
}else if(i!=(f^1)){
low[u]=min(low[u],dfn[v]);
}
}
}
void dfs(int u,int p){
vis[u]=p,ans[p-1].push_back(u);
for(int i=he[u];i;i=e[i].ne){
int v=e[i].to;
if(vis[v]||b[i]) continue;
dfs(v,p);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin>>n>>m;
for(int i=0;i<m;i++) {
int u,v;cin>>u>>v;
if(u==v) continue;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
//ans.push_back(vector<int>());
int id=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
ans.push_back(vector<int>());
dfs(i,++id);
}
}
cout<<id<<endl;
for(int i=0;i<id;i++){
cout<<ans[i].size()<<" ";
for(int j=0;j<ans[i].size();j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
数组逐个解释
| 数组 / 变量 | 开多大 | 含义 | 容易踩的坑 |
|---|---|---|---|
he[N] | n + 5 | 邻接表头指针(存第一条弧的编号) | 用 0 表示「没有」,所以弧编号必须从 1 开始 |
e[M<<1] | 2m 条弧 | to = 终点,ne = 同起点的下一条弧 | 无向边要存两条弧;tot 必须按 2m 算 |
tot | — | 已分配的弧编号,初值 1、先 ++ 再用 | 第 k 条无向边的两条弧正好是 2k 与 2k+1,互为 i^1 |
b[M<<1] | 2m | 这条弧是不是桥 | 两条弧都要标 true,否则染色阶段漏跳 |
dfn[N] | n + 5 | DFS 时间戳,同时兼作「是否访问过」 | if(!dfn[v]) 就是在判「没访问过」 |
low[N] | n + 5 | 从这个子树能回溯到的最小 dfn | 判桥 low[v] > dfn[u]、判割点 low[v] >= dfn[u],符号不同 |
timer | — | 时间戳计数器 | 别起名 time(和库函数冲突) |
vis[N] | n + 5 | 染色阶段用:存分量编号(0 = 未染色) | 名字像 bool,实际存编号;不要写成 vis[u] = 1 |
ans | 动态 | ans[c-1] 存第 c 个分量的所有点 | 下标差 1,写成 ans[p] 会越界或用错桶 |
id | — | 当前分量数(1 开始) | 和 tot(弧编号)、timer(时间戳)别混 |
输出桥
方法 A:判桥时顺手记端点(最省事)
桥一定是在回溯时由父结点那侧判出来的:此时你正站在 u、处理弧 i 指向 v,所以桥就是无向边 {u, v}。
vector<pair<int,int>> br; // ← 新增:所有桥
if(low[v] > dfn[u]){ // 桥
b[i] = b[i^1] = true;
br.push_back({min(u, v), max(u, v)}); // ← 记端点;P1656 要求 u<v
}
输出(P1656 的格式:先排序):
sort(br.begin(), br.end());
cout << br.size() << '\n';
for(auto &p : br) cout << p.first << ' ' << p.second << '\n';
方法 B:按「输入边编号」标记(题目要边号时用)
vector<pair<int,int>> E(m + 1); // E[k] = 第 k 条输入边
int eid[M<<1]; // 弧 -> 输入边编号
bool b[M + 5]; // 按「边编号」标记,不是按弧
void add(int u,int v,int k){ e[++tot].to=v; e[tot].ne=he[u]; eid[tot]=k; he[u]=tot; }
// 建图:add(u,v,k), add(v,u,k)
// 判桥:if(low[v] > dfn[u]) b[eid[i]] = true;
// 输出:for(int k=1;k<=m;k++) if(b[k]) cout << E[k].first << ' ' << E[k].second << '\n';
两个「想当然会写错」的点
- 每条桥只会被记录一次:桥一定是 Tarjan 的树边,只在父侧判一次,所以方法 A 不需要去重。
- 不要事后扫弧:
因为一条无向边有for(int i = 2; i <= tot; i++) if(b[i]) ...; // ✗ 每条桥输出两次2k / 2k+1两条弧,b两条都标了。要扫就判if(i < (i^1)),或者改用方法 B 按边号标记。
要点
- 按「边编号」判父边:
i != (f ^ 1)。存的是双向边,2k与2k+1互为反向,所以父边用异或直接定位。按「点」判父边会在重边上出错。 - 桥的判定:
low[v] > dfn[u],严格大于——等于说明v能回到u,这条边在环上,不是桥。 - 自环:
if (u == v) continue;直接丢掉,自环不影响连通性。 - 染色不用缩点:Tarjan 结束后直接在原图上 DFS,遇到
b[i]为真就跳过,走到的整块就是一个 EBCC。 tot从 1 起:既让 0 能当空指针,又让i^1成对成立。
动画:一步一步看桥是怎么被找出来、分量是怎么被染出来的
动画里的图:1-2-3 一个环、4-5-6 一个环、3-4 与 6-7 两座桥,最终得到 {1,2,3}、{4,5,6}、{7} 三个分量。
易错点 / 易混点
| 问题 | 错误写法 | 正确做法 | 后果 |
|---|---|---|---|
| 判父边 | if(v != fa) 按点判 | if(i != (f^1)) 按边判 | 重边被当成父边,桥漏判 |
| 桥判定 | low[v] >= dfn[u] | low[v] > dfn[u] | 把环边误判成桥 |
| 桥标记 | 只标 b[i] | b[i] = b[i^1] = true | 染色时反方向没跳过,分量粘连 |
| 数组大小 | e[M] / b[M] | e[M<<1] / b[M<<1](2m 条弧) | 越界 RE / 结果随机 |
| 递归深度 | 直接递归 | -Wl,--stack=67108864 或手写栈迭代 | n = 5e5 长链爆栈 |
| 连通性 | 只从 1 号点 DFS | 外层 for(i=1..n) if(!dfn[i]) | 非连通图少算分量 |
| 自环 | 照常建边 | if(u==v) continue; | 不影响正确性,但白占内存 |
vis 语义 | 当 bool 用 | 存分量编号(1,2,3…) | 染色阶段判重出错 |
ans 下标 | ans[p].push_back(u) | ans[p-1].push_back(u)(p 从 1 起) | 越界或错位 |
| 输出顺序 | 排序分量内点 | 题目说任意顺序 | 白花时间还容易写错 |
容易有理解误差的地方(逐条拆)
-
2k/2k+1怎么来的tot初值 1、add里先++tot再用,所以第 1 条无向边占用弧 2 和 3,第 2 条占 4 和 5……即第k条边占2k、2k+1。因此i^1一定是它的反向弧——这就是f^1能识别父边的根本原因。 -
f^1里的f是什么f是父边对应的那条弧编号(tarjan(v, i)传下去的是i,也就是u → v这条弧)。f^1就是它的反向弧v → u。跳过它=不走回头路;但只跳过这一条弧,所以重边(另有一对弧)仍然能被访问到。 -
low为什么用dfn[v]而不是low[v]遇到已访问的点v时,v可能在一个还没跑完的分支里,low[v]还没定型;按定义只看「能不能回到v这个点」,所以用dfn[v]。 -
vis为什么能兼作「访问标记」 因为vis[u] = p里的p ≥ 1,非 0 即「已访问」;同时vis[u]又正好记录了分量号,一举两得——但这也让它看起来像 bool,读代码时容易误会。 -
染色为什么不需要建新图 桥已经标好了,只要在 DFS 时跳过桥边,走到的连通块天然就是 EBCC;缩点建图是多余的。
-
边双 ≠ 点双 边双是删边不连通(桥),点双是删点不连通(割点)。判定式一字符之差:桥
>、割点>=。缩点后:边双缩点是树,点双缩点是圆方树。
代码可以更清楚的地方(可选整理)
原代码能 AC,但有两处让人读起来费劲,可以顺手改:
// 1) vis → col:名字直接说明它是「颜色/分量号」
int col[N]; // 0 = 未染色
void dfs(int u, int c){
col[u] = c;
ans.back().push_back(u); // 2) 不再需要 p-1,直接用刚 push 的桶
for(int i = he[u]; i; i = e[i].ne)
if(!col[e[i].to] && !b[i]) dfs(e[i].to, c);
}
// 调用处:
for(int i = 1; i <= n; i++)
if(!col[i]) { ans.push_back({}); dfs(i, ++id); }
vis改col:消除「bool 还是编号」的歧义;ans[p-1]改ans.back():消除差 1 的下标风险;- 删掉注释掉的
//ans.push_back(...)这类死代码。
复杂度
- 时间:O(n + m)(Tarjan 一遍 + 染色一遍)
- 空间:O(n + m)。
2m条弧:edge8 字节 × 4e6 ≈ 32MB,b4 字节 × 4e6 ≈ 16MB;空间紧张可以把b换成bool/char(省 12MB)。
例题
- 洛谷 P8436【模板】边双连通分量 — 本题
- 洛谷 P1656 炸铁路 — 只求桥,用上面「输出桥 · 方法 A」改几行就能交(记得
sort且u<v)
延伸
- 割点 / 点双连通分量:判定式
low[v] >= dfn[u],注意符号和桥相反;割点把图切成点双连通分量。 - 边双缩点:把每个 EBCC 缩成一个点后得到的是一棵树,树上问题(直径、路径覆盖、边权统计)常在这上面做。