强连通分量（二）——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],dfn[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 稳定婚姻