P8436 【模板】边双连通分量 题解

· · 题解

更新：2022.9.21 修正代码。

前置知识：割边

边双连通分量

概念

若一张无向连通图不存在桥（割边），则称它为“边双连通图”。

无向图的极大边双联通子图被称为“边双联通分量”，简记为“e-DCC”。

在上面的定义中，我们称一个双连通子图 G'=(V',E') “极大”（其中 V'\subseteq V, E'\subseteq E），是指不存在包含 G' 的更大的子图 G''=(V'',E'')，满足 V'\subseteq V''\subseteq V, E' \subseteq E''\subseteq E 并且 G'' 也是双连通子图。

定理

一张无向图时“边双连通图”，当且仅当任意一条边都包含在至少一个简单环中。

求法

只需求出无向图中所有的桥，把桥都删除后，无向图会分成若干个连通块，每一个联通块都是一个“边双连通分量”。

在具体的程序实现中，一般先用 Tarjan 算法标记出所有的桥边。然后，再对整个无向图执行一次深度优先遍历（遍历的过程中不访问桥边），划分出每个连通块。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2000010, M = 6000010;
int head[N], ver[M * 2], Next[M * 2];
int dfn[N], low[N], c[N];//c[x] 表示节点 x 所属的“边双连通分量”的编号。
int n, m, tot = 1, num, dcc;
bool bridge[N * 2];
vector<int> ans[N * 2]; //存储各个连通块及其内部节点编号
void add(int x, int y) {//邻接表存图
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x, int in_edge) { //求割边
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = true;
        }
        else if (i != (in_edge ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
}
void dfs(int x) {
    c[x] = dcc;
    if (x) //防止加入 0
        ans[dcc].push_back(x); 
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (c[y] || bridge[i]) continue;
        dfs(y);
    }
}
int main(){
    ios::sync_with_stdio(false); //关闭与 scanf 的同步来提速
    cin >> n >> m;
    for (register int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    for (register int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);
    for (register int i = 1; i <= n; i++)
        if (!c[i]) {
            ++dcc;
            dfs(i);
        }
    cout << dcc << "\n";
    for (register int i = 1; i <= dcc; i++) { //输出
        cout << ans[i].size();
        for (register int j = 0; j < ans[i].size(); j++)
            cout << ' ' << ans[i][j];
        cout << "\n";
    }
    return 0;
}

推荐

推荐联系配套的点双连通分量。

注：本文抄自 lyd 蓝书。