算法记录-4-（tarjan-无向图连通性）

tarjan--求一张无向图中所有的桥
》》书上的样例

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100010;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],n,m,tot,num;
bool bridge[N<<1];
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]);
    }
}
int main(){
    cin>>n>>m;
    tot=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=2;i<tot;i+=2)
        if(bridge[i])    printf("%d %d\n",ver[i^1],ver[i]);
    return 0;
}

测试数据：

9 11
1 2
1 5
1 6
2 3
2 5
3 4
4 5
6 7
6 8
6 9
8 9

tarjan--求一张无向图中所有的割点
》》书上的样例

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],stack[N];
int n,m,tot,num,root;
bool cut[N];
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[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;
            }
        }
        else    low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)    continue;
        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<=n;i++)
        if(cut[i])    printf("%d ",i);
    puts("are cut-vertexes");
}

测试数据同上
无向图的双连通分量：
边双连通分量(e-DCC)求法

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100010;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],n,m,tot,num;
bool bridge[N<<1];
int c[N],dcc;
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;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        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;
        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=2;i<tot;i+=2)
        if(bridge[i])    printf("%d %d\n",ver[i^1],ver[i]);
    for(int i=1;i<=n;i++)
        if(!c[i]){
            ++dcc;
            dfs(i);
        }
    printf("There are %d e-Dccs.\n",dcc);
    for(int i=1;i<=n;i++)    printf("%d belongs to DCC %d.\n",i,c[i]);
    return 0;
}

e-DCC的缩点

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100010;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],n,m,tot,num;
bool bridge[N<<1];
int c[N],dcc;
int hc[N],vc[N<<1],nc[N<<1],tc;
void add_c(int x,int y){
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
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;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        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;
        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=2;i<tot;i+=2)
        if(bridge[i])    printf("%d %d\n",ver[i^1],ver[i]);
    for(int i=1;i<=n;i++)
        if(!c[i]){
            ++dcc;
            dfs(i);
        }
    printf("There are %d e-Dccs.\n",dcc);
    for(int i=1;i<=n;i++)    printf("%d belongs to DCC %d.\n",i,c[i]);
    tc=1;
    for(int i=2;i<=tot;i++){
        int x=ver[i^1],y=ver[i];
        if(c[x]==c[y])    continue;
        add_c(c[x],c[y]);
    }
    printf("缩点之后的森林，点数%d，边数%d（可能有重边）\n",dcc,tc/2);
    for(int i=2;i<tc;i+=2)    printf("%d %d\n",vc[i^1],vc[i]);
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100010;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],stack[N];
int n,m,tot,num,root,cnt=0,top=0;
bool cut[N];
vector<int> dcc[N];
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    stack[++top]=x;
    if(x==root&&head[x]==0){
        dcc[++cnt].push_back(x);
        return;
    }
    int flag=0;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[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--];
                    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;
    tot=1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)    continue;
        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<=n;i++)
        if(cut[i])    printf("%d ",i);
    puts("are cut-vertexes");
    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;
}

v-DCC的缩点

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100010;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],stack[N],new_id[N];
int n,m,tot,num,root,cnt=0,top=0;
int hc[N],vc[N<<1],nc[N<<1],tc,c[N];
bool cut[N];
vector<int> dcc[N];
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void add_c(int x,int y){
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    stack[++top]=x;
    if(x==root&&head[x]==0){
        dcc[++cnt].push_back(x);
        return;
    }
    int flag=0;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[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--];
                    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;
    tot=1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)    continue;
        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<=n;i++)
        if(cut[i])    printf("%d ",i);
    puts("are cut-vertexes");
    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("");
    }
    num=cnt;
    for(int i=1;i<=n;i++)
        if(cut[i])    new_id[i]=++num;
    tc=1;
    for(int i=1;i<=n;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;
        }
    printf("缩点之后的森林，点数 %d，边数 %d\n",num,tc/2);
    printf("编号 1-%d 的为原图的v-DCC，编号 >%d 的为原图割点\n",cnt,cnt);
    for(int i=2;i<tc;i+=2)    printf("%d %d\n",vc[i^1],vc[i]);
    return 0;
}