Tarjan学习笔记

在最近学习中遇到了几次题解使用Tarjan的情况，便查了一些资料。

算法简介

一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。

前置解释

1.如果有向图两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。
2.如果有向图G的每两个顶点都强连通，称G是一个强连通图。
3.有向图的极大强连通子图，称为强连通分量(strongly connected components)。

举个例子

图1

在图1中，图{1,2,3,4}为一个强连通分量，因为1，2，3，4，都可以两两到达，当然｛5｝，｛6｝也是两个强连通分量。
而我们Tarjan算法的目的就是求解有向图的强连通分量

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

图解模拟有如下定义。

DFN[ i ] : 在DFS中该节点被搜索的次序(时间戳)

LOW[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号

当DFN[ i ]==LOW[ i ]时，为i或i的子树可以构成一个强连通分量。

---

以1号节点为Tarjan 算法的起始点，以DFS序开始搜

顺次DFS搜到节点6，同时更新DFN,LOW

开始回溯，发现LOW[ 5 ]==DFN[ 5 ] , LOW[ 6 ]==DFN[ 6 ] ,则{ 5 } , { 6 } 为两个强连通分量。

拓展节点1 ， 发现1在栈中更新LOW[ 4 ]，LOW[ 3 ] 的值为1

回溯节点1，拓展节点2

至此，Tarjan Algorithm 结束，{1 , 2 , 3 , 4 } , { 5 }　, { 6 } 为图中的三个强连通分量。

时间复杂度

O（E+V）

每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次

参考代码

伪代码

tarjan(u)
{
    DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值
    Stack.push(u)//将节点u压入栈中
    for each(u,v) in E//枚举每一条边
        if (visnotvisted)//如果节点v未被访问过
            tarjan(v)//继续向下找
            Low[u]=min(Low[u],Low[v])
        else if (vinS)//如果节点v还在栈内
                Low[u]=min(Low[u],DFN[v])
    if (DFN[u]==Low[u])//如果节点u是强连通分量的根
    repeat{
        v=S.pop//将v退栈，为该强连通分量中一个顶点
        printv
        until(u==v)
    }
}

C++代码

    void tarjan(int x){
        dfn[x]=low[x]=++tot;//入栈 
        sta[++num]=x;insta[x]=true;
        for(int i=head[x];i;i=edge[i].next){
            if(!dfn[edge[i].to]){
                tarjan(edge[i].to);
                low[x]=min(low[x],low[edge[i].to]);
            }
            else if(insta[edge[i].to])
            low[x]=min(low[x],dfn[edge[i].to]);
        }
        if(low[x]==dfn[x]){
            sa=0;
            do{sa++;insta[sta[num--]]=false;}//弹栈 
            while(x!=sta[num+1]);
            if(sa==2){puts("2");exit(0);}//到2就没必要继续了 
            if(sa>1)ans=min(ans,sa);//取最小值 
        }
    }

以下列出参考的文章，感谢这些作者提供的文章。
1.Tarjan 算法&模板
2.P2661 信息传递 tarjan
3.百度百科-tarjan算法