连通性相关

luckydrawbox · 2023-08-29 22:07:32 · 个人记录

无向图的边双连通分量

求桥

变量

函数

代码

int dfn[N],low[N],num;
bool bri[M<<1];
void tarjan(int x,int in){
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])bri[i]=bri[i^1]=1;
        }
        else if(i!=(in^1))low[x]=min(low[x],dfn[y]);
    }
}

缩点

变量

函数

代码

int dfn[N],low[N],num;
bool bri[M<<1];
int col[N],dcc;
void tarjan(int x,int in){
    dfn[x]=low[x]=++num;
    for(int i=G1.head[x];i;i=G1.nxt[i]){
        int y=G1.ver[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]){
                bri[i]=bri[i^1]=1;
            }
        }
        else if(i!=(in^1))low[x]=min(low[x],dfn[y]);
    }
}
void dfs(int x){
    col[x]=dcc;
    s[dcc]+=a[x];
    for(int i=G1.head[x];i;i=G1.nxt[i]){
        int y=G1.ver[i];
        if(col[y]||bri[i])continue;
        dfs(y);
    }
}

无向图的点双连通分量

求割点

变量

函数

代码

int num,root,dfn[N],low[N];
bool cut[N];
void tarjan(int x){
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        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;
            }
        }
        else
            low[x]=min(low[x],dfn[y]);
    } 
}

圆方树

变量

函数

代码

int dfn[N],low[N],num,cut[N],rt,sta[N],top,dcc;
void tarjan(int x){
    dfn[x]=low[x]=++num;
    sta[++top]=x;
    int flag=0;
    for(int i=G1.head[x];i;i=G1.nxt[i]){
        int y=G1.ver[i],z;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                dcc++;flag++;
                do{
                    z=sta[top--];
                    G2.add(dcc,z);G2.add(z,dcc);
                }while(z!=y);
                G2.add(dcc,x);G2.add(x,dcc);
                if(x!=rt||flag>1)cut[x]=1;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

有向图的强连通分量

缩点

变量

函数

代码

int dfn[N],low[N],num,scc,col[N];
int sta[N],top,ins[N];
void tarjan(int x){
    dfn[x]=low[x]=++num;
    ins[sta[++top]=x]=1;
    for(int i=G1.head[x];i;i=G1.nxt[i]){
        int y=G1.ver[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])low[x]=min(low[x],dfn[y]); 
    }
    if(dfn[x]==low[x]){
        int y;scc++;
        do{
            ins[y=sta[top--]]=0;
            col[y]=scc;
        }while(x!=y);
    }
}
void init(){
    for(int x=1;x<=n;x++)
        for(int i=G1.head[x];i;i=G1.nxt[i]){
            int y=G1.ver[i];
            if(col[x]!=col[y])
                G2.add(col[x],col[y]);
        }
}