无向图的双连通分量

Author： YorkWu
发布时间：March 13, 2019
1186 views
No comments
1260 words
Categories：类目 OI

> 双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点(一条边)都不会改变此图的连通性，即不存在割点(桥)，则称作点(边)双连通图。一个无向图中的每一个极大点(边)双连通子图称作此无向图的点(边)双连通分量。——来自360百科

* * *

#### 边双联通分量（e-DCC）的求法

计算e-DCC只需要把原无向图中所有的桥删去后，会分成若干连通块，每一个连通块都是一个边双联通分量。 一般可以先使用Tarjan求出所有桥，再执行一次dfs，划分出每个连通块。 c\[x\]代表x点所处的边连通分量编号。

#### e-DCC的缩点

把每个e-DCC看做一个节点，把桥看做连接$c\[x\]$和$c\[y\]$的无向边，产生一棵树。

#### 代码如下
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    const int SIZE=100009;
    struct Edge{
        int to,next;
    }e[SIZE*2],ec[SIZE*2];
    int head[SIZE],dfn[SIZE],low[SIZE],num,tot,dcc,c[SIZE];
    int headc[SIZE],totc;
    bool bridge[SIZE];
    int n,m;
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    
    void add_c(int x,int y){
        ec[++totc].to=y;
        ec[totc].next=head[x];
        headc[x]=totc;
    }
    
    void tarjan(int x,int in_edge){
        dfn[x]=low[x]=++num;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(!dfn[y]){
                tarjan(y,i);
                low[x]=min(low[x],low[y]);
                if(dfn[x]<low[y]) bridge[i]=bridge[i^1]=1;
            }
            else if(i!=(in_edge^1)){
                low[x]=min(low[x],dfn[y]);
            }
        }
    }
    
    void dfs(int x){
        c[x]=dcc;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(c[y]||bridge[i]) continue;
            dfs(y);
        }
    }
    
    int main(){
        cin>>n>>m;
        tot=1;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            add(x,y),add(y,x);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) tarjan(i,0);
        }
        cout<<"桥："<<endl;
        for(int i=2;i<tot;i+=2){
            if(bridge[i]) cout<<e[i].to<<" "<<e[i^1].to<<endl;
        }
        for(int i=1;i<=n;i++){
            if(!c[i]) dcc++,dfs(i);
        }
        for(int i=1;i<=n;i++){
            printf("%d属于第%d个dcc\n",i,c[i]);
        }
    
    
    
        //缩点
        totc=1;
        for(int i=2;i<=tot;i++){
            int x=e[i^1].to,y=e[i].to;
            if(c[x]==c[y]) continue;
            add_c(c[x],c[y]);
        }
        printf("缩点后共%d个节点，%d条边\n",dcc,totc/2);
        for(int i=2;i<totc;i+=2){
            cout<<ec[i^1].to<<" "<<ec[i].to<<endl;
        }
        return 0;
    }
```

* * *

#### 点双连通分量（v-DCC）的求法

求出v-DCC，需要维护一个栈，按照如下方法维护栈： 1. 当一个节点被访问时，将它压入栈。 2. 当判定条件$dfn\[x\]\\leq low\[y\]$成立时，无论x是否为根，都需要： 1. 从栈顶不断弹出点，直至y被弹出。 2. 弹出的所有节点与x构成一个v-DCC。 $vector dcc\[i\]$表示第$i$个v-DCC的所有节点

#### v-DCC的缩点

设图中有n个v-DCC,m个割点，这样缩点后形成一张n+m的树。把每个割点与和它相邻的v-DCC相连接。

#### 代码如下
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    const int SIZE=100010;
    struct Edge{
        int to,next;
    }e[SIZE*2];
    int head[SIZE],dfn[SIZE],low[SIZE],strck[SIZE],num,tot,sta,cnt;
    int n,m,root;
    bool cut[SIZE];
    vector<int> dcc[SIZE];
    
    Edge ec[SIZE*2];
    int headc[SIZE],totc,tree_id[SIZE];
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    
    void add_c(int x,int y){
        ec[++totc].to=y;
        ec[totc].next=headc[x];
        headc[x]=totc;
    }
    
    void tarjan(int x){
        strck[++sta]=x;
        dfn[x]=low[x]=++num;
        int flag=0;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(!dfn[y]){
                tarjan(y);
                low[x]=min(low[x],low[y]);
                if(dfn[x]<=low[y]){
                    flag++;
                    if(x!=root||flag>1) cut[x]=1;
                    int z;
                    cnt++;
                    do{
                        z=strck[sta--];
                        dcc[cnt].push_back(z);
                    }while(z!=y);
                    dcc[cnt].push_back(x);
                }
            }
            else low[x]=min(low[x],dfn[y]);
        }
    }
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            add(x,y),add(y,x);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) root=i,tarjan(i);
        }
        printf("有%d个DCC\n",cnt);
        for(int i=1;i<=cnt;i++){
            printf("v-DCC #%d:",i);
            //cout<<dcc[i].size();
            for(int j=0;j<dcc[i].size();j++){
                printf("%d ",dcc[i][j]);
            }
            cout<<endl;
        }
    
        int treec=cnt;
        for(int i=1;i<=n;i++){
            if(cut[i]) tree_id[i]=++treec;
        }
        totc=1;
        for(int i=1;i<=cnt;i++){
            for(int j=0;j<dcc[i].size();j++){
                if(!cut[dcc[i][j]]) continue;
                add_c(i,tree_id[dcc[i][j]]);
                add_c(tree_id[dcc[i][j]],i);
            }
        }
        printf("缩点后共有%d个点，%d条边\n",treec,totc/2);
        printf("编号在[1,%d]的为原图v-DCC,编号大于%d的为原图割点。\n",cnt,cnt);
        for(int i=2;i<totc;i+=2){
            printf("%d %d\n",ec[i^1].to,ec[i].to);
        }
        return 0;
    }
```

Last modification：March 14, 2020