边双连通分量与点双连通分量模板

作者： 作者的头像   qushuka ,  2022-05-03 19:19:30 ,  所有人可见 ,  阅读 354

2


边双连通分量

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 5e4+10, M = 3e5+10;
int h[N],e[M*2],ne[M*2],idx;
//int hc[N],ec[M*2],nec[M*2],idxc;
int dfn[N],low[N],c[N];//c[x]表示节点x所属的“边双连通分量” 
bool bridge[M*2];
int n,m,num,dcc;

void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a], h[a] = idx;
}

//void add_c(int a,int b{
//    ec[++idxc] = b,nec[idxc] = hc[a] , hc[a] = idxc;  
//}

void tarjan(int x,int in_edge){
    dfn[x] = low[x] = ++num;

    for(int i=h[x];i;i=ne[i]){
        int y = e[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;
    for(int i = h[x];i;i = ne[i]){
        int y = e[i];
        if(c[y] || bridge[i]) continue;
        dfs(y);
    }
}

int main(){
    cin >> n >> m;
    idx = 1;
    //idxc = 1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y), add(y,x);
    }
    for(int i=1;i<=n;i++)
       if(!dfn[i]) tarjan(i,0);

    for(int i=1;i<=n;i++)
       if(!c[i]) ++dcc, dfs(i);
    /*
    for(int i=2;i<=idx;i++){
        int x = e[i^1], y = e[i];
        if(c[x] == c[y]) continue;
        add_c(c[x],c[y]);
    }*/
    printf("There are %d e-DCCs.\n",dcc);
    for(int i=1;i<=n;i++)
      printf("%dbelongs to DCC %d.\n",i,c[i]);
    return 0;
}

e-DCC的缩点：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 5e4+10, M = 3e5+10;
int h[N],e[M*2],ne[M*2],idx;
int hc[N],ec[M*2],nec[M*2],idxc;
int dfn[N],low[N],c[N];//c[x]表示节点x所属的“边双连通分量” 
bool bridge[M*2];
int n,m,num,dcc;

void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a], h[a] = idx;
}

void add_c(int a,int b){
    ec[++idxc] = b,nec[idxc] = hc[a] , hc[a] = idxc;    
}

void tarjan(int x,int in_edge){
    dfn[x] = low[x] = ++num;

    for(int i=h[x];i;i=ne[i]){
        int y = e[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;
    for(int i = h[x];i;i = ne[i]){
        int y = e[i];
        if(c[y] || bridge[i]) continue;
        dfs(y);
    }
}

int main(){
    cin >> n >> m;
    idx = 1;
    idxc = 1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y), add(y,x);
    }
    for(int i=1;i<=n;i++)
       if(!dfn[i]) tarjan(i,0);

    for(int i=1;i<=n;i++)
       if(!c[i]) ++dcc, dfs(i);

    for(int i=2;i<=idx;i++){
        int x = e[i^1], y = e[i];
        if(c[x] == c[y]) continue;
        add_c(c[x],c[y]);
    }
    printf("缩点之后的森林,点数%d(可能有重边)\n",dcc,idxc / 2);
    for(int i=2;i<idxc;i+=2)
       printf("%d %d\n",ec[i^1],ec[i]);
    //printf("There are %d e-DCCs.\n",dcc);
    //for(int i=1;i<=n;i++)
     // printf("%dbelongs to DCC %d.\n",i,c[i]);
    return 0;
}

点双连通分量：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 5e4+10, M = 3e5+10;
int h[N],e[M*2],ne[M*2],idx;
int hc[N],ec[M*2],nec[M*2],idxc;
int dfn[N],low[N],c[N];//c[x]表示节点 
vector<int> dcc[N];//dcc[i]保存编号为i的V-DCC(点双连通分量)中得所有节点 
bool cut[N];
int n,m,num,cnt,root;
int stack[N],top;
int new_id[N];

void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a] = idx; 
}
void add_c(int a,int b){
    ec[++idxc] = b,nec[idxc] = hc[a], hc[a] = idxc;
}

void tarjan(int x){
    dfn[x] = low[x] = ++num;
    stack[++top] = x;//当一个节点第一次被访问，把该节点入栈 
    if(x == root && h[x] == 0){//若某个点为孤立点，则它自己构成一个点双连通分量 
        dcc[++cnt].push_back(x);
        return;
    }

    int flag = 0;
    for(int i=h[x];i;i=ne[i]){
        int y = e[i];
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
            if(low[y] >= dfn[x]){
                flag++;
                if(x != root || flag > 1) cut[x] = true;
                cnt++;
                int z;
                do{
                    z = stack[top--];
            //当割点判定法则中的条件dfn[x] <= low[y]成立时，无论x是否为根,都要：
            //   1.从栈顶不断弹出节点，直至节点y被弹出
            //   2.刚才弹出的所有节点与节点x一起构成一个点双连通分量     
                    dcc[cnt].push_back(z); 
                }while(z != y);
                dcc[cnt].push_back(x);
            }
        }
        else low[x] = min(low[x],dfn[y]);
    }

    for(int i=1;i<=cnt;i++){

    }
}

int main(){
    cin >> n >> m;
    idx = 1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }

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

    for(int i=1;i<=cnt;i++){
        printf("v-DCC #%d:",i);
        for(int j = 0;j<dcc[i].size();j++)
           printf(" %d ",dcc[i][j]);//输出每个点双连通分量的节点 
        puts(" ");
    }

    return 0;
}

点双连通分量缩点：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 5e4+10, M = 3e5+10;
int h[N],e[M*2],ne[M*2],idx;
int hc[N],ec[M*2],nec[M*2],idxc;
int dfn[N],low[N],c[N];//c[x]表示节点 
vector<int> dcc[N];//dcc[i]保存编号为i的V-DCC(点双连通分量)中得所有节点 
bool cut[N];
int n,m,num,cnt,root;
int stack[N],top;
int new_id[N];

void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a] = idx; 
}
void add_c(int a,int b){
    ec[++idxc] = b,nec[idxc] = hc[a], hc[a] = idxc;
}

void tarjan(int x){
    dfn[x] = low[x] = ++num;
    stack[++top] = x;//当一个节点第一次被访问，把该节点入栈 
    if(x == root && h[x] == 0){//若某个点为孤立点，则它自己构成一个点双连通分量 
        dcc[++cnt].push_back(x);
        return;
    }

    int flag = 0;
    for(int i=h[x];i;i=ne[i]){
        int y = e[i];
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
            if(low[y] >= dfn[x]){
                flag++;
                if(x != root || flag > 1) cut[x] = true;
                cnt++;
                int z;
                do{
                    z = stack[top--];
            //当割点判定法则中的条件dfn[x] <= low[y]成立时，无论x是否为根,都要：
            //   1.从栈顶不断弹出节点，直至节点y被弹出
            //   2.刚才弹出的所有节点与节点x一起构成一个点双连通分量     
                    dcc[cnt].push_back(z); 
                }while(z != y);
                dcc[cnt].push_back(x);
            }
        }
        else low[x] = min(low[x],dfn[y]);
    }

    for(int i=1;i<=cnt;i++){

    }
}

int main(){
    cin >> n >> m;
    idx = 1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }

    for(int i=1;i<=n;i++)
       if(!dfn[i]) root = i,tarjan(i);
    /*  
    for(int i=1;i<=cnt;i++){
        for(int j = 0;j<dcc[i].size();j++)
           printf("%d ",dcc[i][j]);//输出每个点双连通分量的节点 
        puts(" ");
    }
    */

    //以下为V-DCC的缩点 
    num = cnt;//给每个割点一个新的编号，编号从cnt + 1开始 
    for(int i=1;i<=n;i++)
       if(cut[i]) new_id[i] = ++num;
    //建新图，从每个V-DCC到它包含的所有割点连边 
    idxc = 1;
    for(int i=1;i<=cnt;i++){//遍历连通分量 
        for(int j=0;j<dcc[i].size();j++){
            int x = dcc[i][j];
            if(cut[x]){//如果是割点 
                add_c(i,new_id[x]);
                add_c(new_id[x],i);
            }
            else c[x] = i;//除割点外，其他点仅属于1个V-DCC 
        }   
    }
    printf("缩点之后的森林,点数 %d, 边数 %d\n",num,idxc / 2); 
    printf("编号1~%d 的为原图的V-DCC,编号 >%d 的为原图割点\n",cnt,cnt);
    for(int i=2;i<idxc;i+=2)
       printf("%d %d\n",ec[i^1],ec[i]);

    return 0;
}

0 评论

1024
x