Tarjan初步-边双联通分量

前言

本来应该先说强连通分量，但是有一定的分配，所以这个在下一篇博客将会见到。

这个本想连点连通分量一起讲，但是量有点大，所以我就分两步讲。

边双

定义

核心概念:没有割边;

割边只会把图分成两部分对图中的点没有影响;

再来看看图解

很容易就能发现，只要将割边断掉，然后剩下的连通块就是我们的边双，那么我们的代码就可以yy出来了，先跑一遍Tarjan求割点，然后在去跑dfs，将每一个边双染色，那么就可以了,而染色操作，以便于我们后面好缩点。

我们来看模板

void Tarjan(int x,int fa){
    low[x]=dfn[x]=++t;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!dfn[y]){
            Tarjan(y,i);
            low[x]=min(low[y],low[x]);
            if(low[y]>dfn[x]) 
                edge[i].flag=edge[(i^1)].flag=1;//寻找割边 ，并标记 
        }else if((i^1)!=fa){
            low[x]=min(low[x],dfn[y]);
        }
    }
}

void dfs(int x){
    col[x]=tot;//染色 
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!col[y]&&!edge[i].flag)//不能是走过的点和割边 
            dfs(y);//遍历 
    }
}

//下面插入主函数中

for(int i=1;i<=n;i++){
        if(!dfn[i]) Tarjan(i,-1);
    }
for(int i=1;i<=n;i++){
    if(!col[i]) ++tot,dfs(i);
}

大家仔细琢磨一下，应该就能懂他的思想了。

例题1：

这道题很显然是将这个图变为边双。在同一个边双连通分量中，任意两点都有至少两条独立路可达，所以同一个边双连通分量里的所有点可以看做同一个点。 这时就要用到我们的染色缩点，缩点请仔细思考怎么做。

缩点后，新图是一棵树，树的边就是原无向图的桥。 现在问题转化为：在树中至少添加多少条边能使图变为双连通图。

此时我们就能想出之前我们学过的入度和出度；

那么，只要将度为一的点连边即可，那么此时我们的公式就是添加边数=（树中度为1的节点数+1）/2；

具体做法就是：

首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。 然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是 $(leaf+1)/2$ 次，把所有点收缩到了一起。

这样就解决了，来看

Code

#include<bits/stdc++.h>
#define maxn 5007
#define M 20007
using namespace std;
int n,m,t,head[maxn],cent=1,low[maxn],dfn[maxn],vis[maxn];
int tot,col[maxn],out[maxn],ans,in[maxn],ol;
struct node{
    int next,to,flag,from;
}edge[M<<1];

void add(int u,int v){
    edge[++cent]=(node){head[u],v,0,u};head[u]=cent;
}

void Tarjan(int x,int fa){
    low[x]=dfn[x]=++t;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!dfn[y]){
            Tarjan(y,i);
            low[x]=min(low[y],low[x]);
            if(low[y]>dfn[x]) 
                edge[i].flag=edge[(i^1)].flag=1;//寻找割边 ，并标记 
        }else if((i^1)!=fa){
            low[x]=min(low[x],dfn[y]);
        }
    }
}

void dfs(int x){
    col[x]=tot;//染色 
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!col[y]&&!edge[i].flag)//不能是走过的点和割边 
            dfs(y);//遍历 
    }
}

void make_dfs(int x,int fa){
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(y==fa) continue;
        out[y]++,in[x]++;//计算入度出度 
        make_dfs(y,x);
    }
}

int main(){
//    freopen("rpaths.in","r",stdin);
//    freopen("rpaths.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        if(a==b) continue;
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) Tarjan(i,-1);
    }
    for(int i=1;i<=n;i++){
        if(!col[i]) ++tot,dfs(i);
    }
    memset(head,0,sizeof(head));cent=1;//预处理 
    for(int i=2;i<=2*m+1;i++){
        if(edge[i].flag){
            add(col[edge[i].from],col[edge[i].to]);
        }//重点！！！染色缩点建树 
    }
    make_dfs(1,-1);//寻找度 
    for(int i=1;i<=tot;++i){
        if((out[i]==1&&in[i]==0)||(in[i]==1&&!out[i])){
            ans++;//统计度为一的点 
        }
    }
    printf("%d\n",(ans+1)/2);
}

例题2

我们只要缩点，然后求距离就可以了，LCA求距离都懂的吧？（好像又没讲，下次下次）；

我的错，没说LCA，在讲完LCA后再来看这道吧，但看完后就懂代码了：

Code

#include<bits/stdc++.h>
#define maxn 100007
using namespace std;
int n,m,cent=1,head[maxn],low[maxn],dfn[maxn],col[maxn],t,fa[maxn][30];
int tot,dep[maxn],q;
struct node{
    int next,to,from,flag;
}edge[maxn<<2];

void add(int u,int v){
    edge[++cent]=(node){head[u],v,u,0};head[u]=cent;
}

void make_dfs(int x,int dy){
    dep[x]=dy;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(fa[x][0]==y) continue;
        fa[y][0]=x;
        make_dfs(y,dy+1);
    }
}

void Init(){
    fa[1][0]=-1;
    make_dfs(1,0);
    for(int i=1;i<=25;i++){
        for(int j=1;j<=tot;j++){
            if(fa[j][i-1]<0) fa[j][i]=-1;
            else fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    }
    return ;
}

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=0,d=dep[x]-dep[y];d;d>>=1,i++){
        if(d&1) x=fa[x][i];
    }
    if(x==y) return x;
    for(int i=25;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}

void Tarjan(int x,int f){
    low[x]=dfn[x]=++t;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!dfn[y]){
            Tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) 
                edge[i].flag=edge[(i^1)].flag=1;
        }else if((i^1)!=f){
            low[x]=min(low[x],dfn[y]);
        }
    }
}

void dfs(int x){
    col[x]=tot;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(!col[y]&&!edge[i].flag)
            dfs(y);
    }
}

int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) Tarjan(i,-1);
    }
    for(int i=1;i<=n;i++){
        if(!col[i]) ++tot,dfs(i);
    }
    memset(head,0,sizeof(head));cent=1;
    for(int i=2;i<=2*m+1;i++){
        if(edge[i].flag){
            add(col[edge[i].from],col[edge[i].to]);
        }//缩点套路，一定要会 
    }
    Init();//LCA初始化 
    scanf("%d",&q);
    for(int i=1,a,b;i<=q;i++){
        scanf("%d%d",&a,&b);
        printf("%d\n",dep[col[a]]+dep[col[b]]-2*dep[lca(col[a],col[b])]);//求距离 
    }
}

这就差不多结束了，自己可以在找些题，要深刻理解缩点的重要性;