强连通分量(二)——tarjan

开这篇文章之前可以先看一下强连通分量(一)——kosaraju。个人认为kosaraju要更容易理解一些,但是要慢一些。一些概念性的东西在这篇博客中就不作说明了。

接下来我们直接进入主题:tarjan

tarjian的复杂度和kosaraju一样,都是O(n+m),但是kosaraju一般丑一些常数大一些,而且面临的爆栈风险也更大,因此tarjan算法要更常用一些(tarjan的效率比kosaraju高30%左右)。当然,我个人认为kodaraju可以为理解tarjan算法做一些铺垫,这个因人而异吧qwq。

tarjan算法是基于DFS的。我们首先建立一个栈。对于每个节点,我们记录两个值:dfn和low。其中,dfn表示该节点的搜索序号,而low表示此节点能到达的栈中dfn最小的节点。

对于每次搜索,我们首先将当前节点加入栈中,然后记录下当前节点的dfn,同时将low设置为dfn相等。接下来我们就开始便利该节点的子节点。。。对于没有被访问过的子节点,我们直接更新当前节点的low值为当前值和其子节点的low值的最小值。如果我们发现此节点有一个子节点被访问过且这个节点在栈中(即不属于任何强连通分量,因为所有节点只要被访问过且不在栈中,那么其必定属于了一个强连通分量),那么我么就更新这个节点的low为当前值和此子结点的low值的最小值。

回溯时,我们将每个节点的low更新为它的所有子节点的low值的最小值。这样,我们不难发现,如果当前节点的low值等于dfn值,那么它显然对于我们搜索的顺序上来说是强连通分量的顶点,因此我们将栈中的所有节点开始挨个弹出直到当前节点。我们弹出的所有节点就组成了一个强连通分量。

下面给出代码(说明:路径使用邻接表存储):

void tarjan(int k)
{
    ++sum;
    dfn[k]=sum;
    low[k]=sum;
    st[++top]=k;//入栈
    int d=head[k];
    while(d!=0)
    {
        if(!dfn[a[d].v])//如果当前节点没有被搜过
        {
            tarjan(a[d].v);//向下搜
            low[k]=min(low[k],low[a[d].v]);//更新low
        }
        else
            if(!co[a[d].v])//如果当前节点被搜过且在栈中
                low[k]=min(low[k],low[a[d].v]);//更新low
        d=a[d].next;
    }
    if(dfn[k]==low[k])//如果当前节点是强连通分量的顶点
    {
        col++;
        while(dfn[st[top]]!=low[st[top]])
        {
            num[col]++;
            co[st[top]]=col; 
            top--;
        }
        co[st[top]]=col;
        num[col]++;
        top--;//从栈中弹出此强连通分量
    }
    return;
}

相关练习:BZOJ 1051 [HAOI2006]受欢迎的牛BZOJ 2140 稳定婚姻

发表评论

电子邮件地址不会被公开。 必填项已用*标注