连通性问题（3）- 双连通分量

在阅读本文前，请确认你掌握了割点和桥的求法，否则请先阅读 连通性问题（2）- 割点和桥。

概念

仿照强连通分量，我们来定义边双连通分量和点双连通分量。

• 边双连通分量：原图的一个极大边双连通子图。
• 点双连通分量：原图的一个极大点双连通子图。

边双连通分量

洛谷P8436 【模板】边双连通分量

边双连通分量求解十分简单。只需把原图中的所有桥删去，在新图上所求得的连通分量就是边双连通分量。

求边双连通分量可以使用并查集或 dfs 求连通分量。

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5+5;

struct Edge{
    int u,v;
    bool flag;
};

vector<Edge> edges;
vector<int> G[N];

int dfn[N],low[N],dfs_clock;
int fa[N];

void tarjan(int u){
    dfn[u]=low[u]=++dfs_clock;
    for(int eid:G[u]){
        int v = edges[eid].v;
        if(v==fa[u])continue;

        if(!dfn[v]){
            fa[v]=u;
            tarjan(v);
            low[u]=min(low[v],low[u]);
            if(low[v] > dfn[u]){
                edges[eid].flag=edges[eid^1].flag=1;
            }
        }
        else{
            low[u]=min(low[u],low[v]);
        }
    }
}

int ecc[N];
int find(int x){
    return ecc[x]==x?x:ecc[x]=find(ecc[x]);
}
void merge(int i,int j){
    ecc[find(i)]=find(j);
}

vector<int> ans[N];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        edges.push_back({u,v,0});
        edges.push_back({v,u,0});
        int cn = edges.size();
        G[u].push_back(cn-2);
        G[v].push_back(cn-1);
    }

    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }

    for(int i=1;i<=n;i++){
        ecc[i]=i;
    }

    for(auto e:edges){
        if(e.flag)continue;
        merge(e.u,e.v);
    }

    int cnt = 0;

    for(int u=1;u<=n;u++){
        ans[find(u)].push_back(u);
        if(find(u)==u)cnt++;
    }

    printf("%d\n",cnt);
    for(int i=1;i<=n;i++){
        if(find(i)!=i)continue;
        printf("%llu ",ans[i].size());
        for(int v:ans[i]){
            printf("%d ",v);
        }
        puts("");
    }

    return 0;
}

注意重边的处理。若需要处理带重边的图，只需分别储存每条边是否是桥边即可。这样重边一条会被标记为桥，另一条不会被标记，可以正确地找出边双连通分量。

点双连通分量

洛谷P8435 【模板】点双连通分量

需要注意的是，点双连通分量之间存在公共点，并且这些公共点一定是割点。

我们来考虑如何在求割点的基础上编写求解点双代码。

考虑上图中的割点 $u'$ 和 $u$。可以看到，此时 $u$ 、$u$ 的子树 $v$ 和 $u'$ 构成了一个点双连通分量，$u'$ 和 $v'$ 构成了一个点双连通分量。我们考虑用一个栈存点。当找到割点时，在当前连通分量的点是在栈中直到割点子节点 $v'$ 的节点和割点 $u'$（即图中蓝绿色子树和节点 $u'$）。特别的，不能将割点 $u$ 弹出栈，因为在后续，$u'$ 还可能加入其他连通分量（$u'$ 同时还在粉色连通分量中）。

再来考虑根。在求点双的时候和割点不同，无需特殊处理。这是因为根节点一定在某个点双中，需要进行处理（而 low[v]>=dfn[u] 对于根节点恒成立）。因此，无需在 dfs 判断 low[v]>=dfn[u] 是再同时判断 u!=root 了。

最后需要特判一下孤立点即可。对于孤立点，每个点就是一个连通分量。

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5+5;

vector<int> G[N];
vector<int> ans[N];
int cnt;

stack<int> s;
int dfn[N],low[N],dfs_clock;

void tarjan(int u,int fa){
    // printf("tarjan %d,%d\n",u,fa);
    dfn[u]=low[u]=++dfs_clock;
    s.push(u);
    int son = 0;
    for(int v:G[u]){
        if(!dfn[v]){
            son++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);

            if(low[v] >= dfn[u]){
                while(s.top()!=v){
                    ans[cnt].push_back(s.top());
                    s.pop();
                }
                s.pop();
                ans[cnt].push_back(v);
                ans[cnt].push_back(u);
                cnt++;
            }
        }
        else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(u==fa && son==0){
        ans[cnt++].push_back(u);
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,i);
    }

    printf("%d\n",cnt);
    for(int i=0;i<cnt;i++){
        printf("%lu ",ans[i].size());
        for(auto x:ans[i]){
            printf("%d ",x);
        }
        puts("");
    }
    return 0;
}