\(Tarjan\)算法在无向图中的应用

无向图的割点与桥

设无向连通图\(G=(V,E)\),

若对于\(x \in V\),从图中删去节点\(x\)以及所有与\(x\)关联的边之后,\(G\)分裂成两个或两个以上不相连的子图,则称\(x\)为\(G\)的割点.(简单定义:删掉这个点之后,图不再连通,则这个点是割点).

若对于\(e \in E\),从图中删去边\(e\)之后,\(G\)分裂成两个不相连的子图,则称\(e\)为\(G\)的桥或割边.(简单定义:删掉这条边之后,图不再连通,则这条边是割边)

在无向图中任选一个节点出发进行深度优先遍历，每个点只访问一次.所有发生递归的边\((x,y)\)构成一棵树,我们把它称为“无向连通图的搜索树”，当然一般无向图（不一定连通）的各个连通块的搜索树构成无向图的“搜索森林”.

在图的深度优先遍历的过程中，按照每一个节点第一次被访问的时间顺序，给予\(n\)个节点\(1~n\)的整数标记，该标记就被称为“时间戳”.记为\(dfn[x]\)(简单定义:\(dfs\)的遍历顺序)

“追溯值”\(low[x]\).设\(subtree(x)\)表示搜索树中以\(x\)为根的子树.\(low[x]\)定义为以下两种节点的时间戳最小值：

1.\(subtree(x)\)中的节点.

2.通过一条不在搜索树上的边，能够到达\(subtree(x)\)中的节点（就是与搜索树中以\(x\)为根的子树以不在搜索树上的边相连的节点）.

割边判定法则:无向边\((x,y)\)是割边，当且仅当搜索树上存在\(x\)的一个子节点\(y\)，满足:\(dfn[x]<low[y].\)(很好理解,\(y\)在不经过\((x,y)\)这条边的前提下,无论如何都无法到达x或比x更早访问的节点,所以切掉\((x,y)\)这条边之后,\(x,y\)就被分割到了两个部分.)

inline void add(int a,int b){
    nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u,int in_edge){
    dfn[u]=low[u]=++timeclock;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){//搜索树上v是u的子节点
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])bridge[i]=bridge[i^1]=1;//标记是否是桥边
        }
        else if(i!=(in_edge^1)){//无向边(u,v)不在搜索树上
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main(){
    n=read();m=read();tot=1;//注意这个tot的初始值是1不是0
    for(int i=1;i<=m;++i){
        a[i]=read();b[i]=read();
        add(a[i],b[i]);add(b[i],a[i]);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
    ...
    return 0;
}

割点判定法则:若\(x\)不是搜索树的根节点(深度优先遍历的起点),则\(x\)是割点当且仅当搜索树上存在\(x\)的一个子节点\(y\),满足:\(dfn[x]<=low[y]\).

特别地,如果\(x\)是搜索树的根节点,那么\(x\)是割点当且仅当搜索树上存在至少两个子节点满足上述条件.

inline void tarjan(int x){
    dfn[x]=low[x]=++timeclock;
    int child=0;//记录子节点数量
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                child++;
                if(x!=root||child>=2)cut[x]=1;//标记x是割点
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    ...
    
    for(int i=1;i<=n;i++)
        if(!dfn[i])root=i,tarjan(i);
        
    ...
}

洛咕---[模板]割点

推荐一道题 与割点相关 的题

无向图的双连通分量

若一张无向连通图不存在割点,则称它为"点双连通分量".若一张无向连通图不存在桥,则称它为"边双连通分量".无向图的极大点双连通子图称作"点双连通分量(\(v-DCC\))",无向图的极大边双连通子图称作"边双连通分量(\(e-DCC\))."

边双连通分量\((e-DCC)\)的求法:先求出图中所有的桥(割边),把桥边都删掉之后,图就会分成若干个连通块,每个连通块都是一个"边双连通分量".

代码建立在已经用\(Tarjan\)标记了所有的桥边的情况下:

inline void dfs(int x){
    belong[x]=dcc;//编号为x的节点属于第dcc个边双连通分量
    for(int i=head[x];i;i;=nxt[i]){
        int y=to[i];
        if(belong[y]||bridge[i])continue;
//如果点y已经遍历过 或者 (x,y)之间的边是桥边,则跳过
        dfs(y);
    }
}
int main(){
    ...
    
    for(int i=1;i<=n;++i)
        if(!belong[i]){//划分每个点属于哪个边双连通分量
            ++dcc;
            dfs(i);
        }
    
    ...
}

边双连通分量\((e-DCC)\)的缩点:在上述求出边双连通分量\((e-DCC)\)并划分出每个连通块之后,把每个\(e-DCC\)都看作一个节点,然后桥边看作连接节点之间的边,则原来的无向连通图构成了一棵树,这就是缩点操作了.具体代码实现的话,就枚举每条边,如果两个端点不在同一个\(e-DCC\)内,那么这条边就加入新的图中.

e-DCC例题

点双连通分量\((v-DCC)\)的求法:

1.若某个节点为孤立点,则它自己单独构成一个\(v-DCC\).

2.除了孤立点之后,\(v-DCC\)的大小至少为2.

3.桥不属于任何\(v-DCC\),但是割点可能属于多个\(v-DCC\).

inline void tarjan(int x){
     dfn[x]=low[x]=++tim;st[++top]=x;
     if (x==root&&head[x]==0){
         dcc[++cnt].push_back[x];
         return;
     }
     int flag=0;
     for(int i=head[x];i;i=nxt[i]){ 
         int y=to[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=st[top--];
                     dcc[cnt].push_back[z];
                 }while(z!=y) 
                dcc[cnt].push_back[x];     
             }
         }
         else low[x]=min(low[x],dfn[y]);         
     }  
}
int main(){
    ...
    
    for(int i=1;i<=cnt;i++)
        for(int j=0;j<dcc[i].size();j++)
            printf("%d", dcc[i][j]);
    ...
}   

点双连通分量\((v-DCC)\)的缩点:设图中有\(p\)个割点和\(t\)个\(v-DCC\),那么我们建立一张包含\(p+t\)个节点的新图,把每个\(v-DCC\)和每个割点作为新图中的节点,并在每个割点与包含它的所有\(v-DCC\)之间连边.这个新图就是一棵树.

代码建立在上面求点双连通分量\((v-DCC)\)的基础之上:

num=cnt;
//cnt表示的是图中v-DCC的个数
for(int i=1;i<=n;++i)
    if(cut[i])new_id[i]=++num;
//给每个割点一个新的编号,从cnt+1开始
tot_c=1;
//重新建图的边的总数,从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]){//在割点和包含它的v-DCC之间连边
            add_c(i,new_id[x]);
            add_c(new_id[x],i);
        }
        else belong[x]=i;//割点之外的点,只会属于一个v-DCC
    }

v-DCC例题

\(Tarjan\)算法在有向图中的应用

有向图的强连通分量:

强连通:在一个有向图\(G\)里，设两个点\(a,b\)，由\(a\)有一条路可以走到\(b\)，由\(b\)有一条路可以走到\(a\)，我们就叫这两个顶点\((a,b)\)强连通.策划那个这个有向图是强连通图.

有向图的极大强连通子图称为"强连通分量",简记为\(SCC\).

void add(int a,int b){
    nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
void tarjan(int u){
    dfn[u]=low[u]=++timeclock;
    st[++top]=u;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!color[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){//满足强连通分量的条件
        color[u]=++cnt;
        while(st[top]!=u){
            color[st[top]]=cnt;
            top--;
        }
        top--;
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int a,b;
        a=read();b=read();
        add(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
//至于最后输出什么,就看题目求什么了;
//总之,我们已经得到了强连通分量的个数cnt
//每个点分别属于哪个强连通分量(color数组记录)
    return 0;
}

把强连通分量缩点会得到一张有向无环图\(DAG\).

    for(int x=1;x<=n;++x)
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(color[x]==color[y])continue;
            add_c(color[x],color[y]);
//如果这条有向边的两个端点不属于同一个强连通分量
//则在这两个强连通分量之间连边,边的方向保持不变
        }

有向图的必经点与必经边:

给定一张有向图,起点\(S\),终点\(T\).若从\(S\)到\(T\)的每条路径都经过一个点\(x\),则称点\(x\)是有向图中从\(S\)到\(T\)的必经点.

从\(S\)到\(T\)的每条路径都经过一条边\((x,y)\),则称这条边是有向图中从\(S\)到\(T\)的必经边或桥.

计算有向无环图\(DAG\)中的必经点与必经边:

1.在原图上按照拓扑序进行动态规划,求出起点\(S\)到图中每个点\(x\)的路径条数\(fs[x]\).

2.在反图上再次按照拓扑序进行动态规划,求出图中每个点\(x\)到终点\(T\)的路径条数\(ft[x]\).

显然,\(fs[T]\)表示从\(S\)到\(T\)的路径总条数.根据乘法原理:

1.对于一个点x,若\(fs[x]*ft[x]=fs[T]\),则\(x\)是有向无环图上\(S\)到\(T\)的必经点.

2.对于一条有向边\((x,y)\),若\(fs[x]*ft[y]=fs[T]\),则\((x,y)\)是有向无环图上\(S\)到\(T\)必经边.

Tarjan算法相关(学习笔记)

原文：https://www.cnblogs.com/PPXppx/p/11590709.html