【蒟蒻图论】tarjan及其经典运用(二)

上篇博客我们重点讲解了tarjan算法的实现以及它最重要的用法——求解强连通分量。这篇博客我们就继续学习一下tarjan的其他经典用法。

运用tarjan求割点

什么是割点

在无向连通图中,如果将其中一个点以及所有连接该点的边去掉,图就不再连通,那么这个点就叫做割点(cut vertex / articulation point)

例如,在下图中,0、3是割点,因为将0和3中任意一个去掉之后,图就不再连通。如果去掉0,则图被分成1、2和3、4两个连通分量;如果去掉3,则图被分成0、1、2和4两个连通分量。
1.png

如何用tarjan求解

上一篇关于tarjan的博客中我们说过,tarjan是基于DFS的。所以在tarjan过程中,我们会在图上DFS出一颗或几颗(如果图不连通)解答树。

我们仍以刚刚那幅图为例子:2.PNG
若以0为根节点,那么我们的DFS树就可能会如上图所示的红边一般。

然后我们很自然的根据tarjan算法,会求出每个点i的dfn[i]和low[i],顺便再记录一下每个点在解答树上的儿子数量child[i]和每个节点的父亲fa【i】(若fa【i】==0,那么i就是根节点)。

然后我们分类讨论一下i,如果i是根节点,那么我们很明显的发现如果i有两个以上的儿子,则i为割点。(因为这棵树是DFS出来的,如果存在两个以上的子树,那么根节点就是这几个儿子互相到达的必经节点【若不是必经节点,那在之前的DFS中应该早就DFS出来了,不会成为根节点的另一个儿子!!!】)代码如下:

if(fa[x]==0 && child[x]>=2)bj[x]=1;

那么如果i不是根节点呢?首先如果i是叶子节点(i无儿子),那么i肯定不是割点。如果i不是叶子节点,且i有儿子j不能回到i的上面(即low[j] >= dfn[i]),那么i如果消失,那么他的那个儿子j所在的子树肯定也和i的父亲所在的子树不相连了,成了两个联通块如下图:
3.PNG

但如果j能够回到i的上面(即low[j] < dfn[i]),那么i如果消失,j也依然和上面相连,如下图:
4.PNG

具体代码如下:

if(fa[x]>0 && low[y]>=dfn[x])bj[x]=1;

所以总的代码如下:

int tarjan(int x)
{
    tot++;dfn[x]=tot;low[x]=tot;
    stack[++indexx]=x;
    visit[x]=1;

    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(dfn[y]==0)
        {
            fa[y]=x;child[x]++;
            tarjan(y);
            low[x]=my_min(low[x],low[y]);
            if(fa[x]==0 && child[x]>=2)bj[x]=1;
            if(fa[x]>0  && low[y]>=dfn[x])bj[x]=1;
        }
        else if(visit[y]==1)low[x]=my_min(low[x],dfn[y]);

    }

    if(dfn[x]==low[x])
    {
        do
        {  
            visit[stack[indexx]]=0;  
            indexx--;  
        }
        while(x!=stack[indexx+1]);

    }
    return 0;

}

一些需要注意的点

在之前的tarjan求强连通的算法中,我们在处理访问到已经访问过的点的操作是

if(visit[y]==1)low[x]=my_min(low[x],low[y]);

但这样的话就会WA掉,我们要改成

if(visit[y]==1)low[x]=my_min(low[x],dfn[y]);

这是因为关于tarjan算法,一直有一个很大的争议,就是low[u]=min(low[u],dfn[v]);

这句话,如果改成low[u]=min(low[u],low[v])就会wa掉,但是在求强连通分量时却没有问题

根据许多大佬的观点,在求强连通分量时,如果v已经在栈中,那么说明u,v一定在同一个强连通分量中,所以到最后low[u]=low[v]是必然的,提前更新也不会有问题,但是在求割点时,low的定义有了小小的变化,不再是最早能追溯到的祖先,(因为是个无向图)没有意义,应该是最早能绕到的割点,为什么用绕到,是因为是无向边,所以有另一条路可以走,如果把dfn[v]改掉就会上翻过头,可能翻进另一个环中,所以wa掉。需要特别注意。

运用tarjan求割边

什么是割边

割边:如果去掉某一条边之后,联通分量的数目变多,那么这个点就是割边;

换言之,就是如果对于一个连通图,去掉边(u,v)后,图就不连通了,那么这条边(u,v)就是我们要求解的割边了!

如何用tarjan求解

还是利用low[u]数组和dfn[u]数组来判断割边,对于任意一条边(u,v)【我们假定我们先发现u,即dfn【u】小于dfn[v]】:那么如果它是割边的话,就有low[v] > dfn[u] ,也就是以v为根的子树是封闭的,无法回到u点或u以上的点,只要去掉u,v连接的这条边,就会增加联通分量的数量,所以这条边(u,v)就是一条割边了。

lll.PNG

程序部分

void tarjan ( int u , int p )    
{    
    dfn[u] = low[u] = ++times;    
    for ( int i = head[u] ; ~i ; i = e[i].next )    
    {    
        int v = e[i].v;    
        if ( !dfn[v] )    
        {    
            tarjan(v,u);    
            low[u] = min ( low[u] , low[v] );    
            if ( low[v] > dfn[u] && !e[i].tag )    
                ans.push_back ( e[i].id );    
        }    
        else if ( v != p )    
            low[u] = min ( low[u] , dfn[v] );    
    }    
}    

运用tarjan进行缩点

什么是缩点呢?就是把每个强连通分量都当成一个超级节点,然后再把这个强连通分量每个点的信息合并到这个超级节点上:比如连边啊,点权啊什么什么的,具体要按照题目来定。如下图:
5.png6.png

具体的代码只要在确定强连通分量后的那一段进行修改:
(color【i】=j表示第i个点属于第j个强连通分量【也就是超级节点里】)

if(dfn[x]==dfn[x])
    {
        tot++;//记录这是第几个强连通
        while(stack[indexx+1]!=x)
        {
            color[stack[indexx]]=tot;//修改所属强连通
            sum[tot]+=val[stack[indexx]];//点权合并 
            visit[stack[indexx--]]=0;
        }
    }

结语

那么到这里,tarjan就告一段落了,接下来如果我看到有其他经典的用法再来填坑吧!希望你喜欢这篇博客!

Last modification:July 12th, 2018 at 09:29 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment