首页 > 代码库 > Tarjan的强联通分量

Tarjan的强联通分量

  求强联通分量有很多种。 《C++信息学奥赛一本通》  中讲过一个dfs求强联通分量的算法Kosdaraju,为了骗字数我就待会简单的说说。然而我们这篇文章的主体是Tarjan,所以我肯定说完之后再赞扬一下Tarjan大法好是不是

  首先我们讲一下强联通分量

  强联通分量指的是图的一个子图。在这个子图中,任意两个节点都可以互相到达。从定义上我们就可以看出是一个有向图来,因为任意一个无向图都符合该定义。

  而它的标准定义是:有向图中任意两点都联通的最大子图。

                     技术分享

  咳咳,首先庆祝一下哈——本人博客的第一张图。绘图历时3分钟。

  在咱们举的例子中,可以看出1 、2 、3 、5 通过边可以相互到达,它们算一个强联通分量,但4却被它们隔绝在外。从图中可以看出,从4点出发不能到达任意一个点。所以它单个节点也算一个强联通分量。所以图中的强联通分量有两个:一个是1-2-3-5,一个是4。

  ok看完了强联通分量是什么我们就讲一下Kosaraju。

  这个算法的思路是,对图进行DFS并记录每个点的退出顺序。再构造反图(就是有向边的方向全都反过来),按照退出顺序的逆序DFS反图,对得到的点进行染色即为强联通分量。

  讲完思路开始模拟。以起点1为起点遍历顺序如下:

  [ 1 2 3 5 4  5 3 2 4 4 1 ]

  加粗斜体外带下划线的部分就是本图的退出顺序。

  于是我们得到这样一个数组:[ 5 3 2 4 1 ] 。按照这个数组的逆序对反图遍历得到:

  [ 5 3 2 1 退出 4 退出 ]

  即得到要求的两个强联通分量。

  还要两遍DFS,麻烦的一比。看我大Tarjan一遍DFS就能求出强联通分量

  首先我们要明确Tarjan要用到的两个数组:dfn[] 和 low[] 

  dfn指的是在DFS过程中访问到该点的顺序。从1开始DFS全图,那么1的dfn值就是1,2的dfn值是2,5的dfn值是4,4的dfn值是5。剩下的一个类推

  那么low呢?low指的是如果逆着DFS序往前回溯,该节点最早是由哪个节点走过来的。

  比如在上图中2 、3 、5 、4 最早都是由1走过来的,所以它们的low值都是1

  下面贴出dfn和low的算法

每次dfs(点u){

  dfn[u] = 进入 dfs() 函数的次数  (自己定义一个时间戳记录 如 timee)

       枚举与其相邻的点v{

          如果 没有 访问过点v {   ( 就是dfs树上的树边 )

        dfs(v);

        如果 v 能追溯 到 比“u 追溯到的最早的点” 更早的点;

        那么 u 就能 通过 v 来追溯到 那个点;

        low[u]=min(low[u],low[v]);

      }

       如果 访问过点v && v在栈中

       low[u]=min(low[u],dfn[v]); 

     }

  缩点

}

  上面那些伪代码是从伟大的GeneralLiu那里带过来的,在此先%%%

  然后  假设我们走到一个节点i,发现这个i不能继续扩展了,也就是dfn[i]==low[i]

  于是我们开始往回走。往回走的过程中,我们就把和它一个分量的节点进行染色,给它们统一的标记。  最后统计有多少种不同的标记即是强联通分量个数

  luogu的一道题刻录光盘非常好,可以用于练手。

  放代码

#include<iostream>
#include<cstring>
using namespace std;
int head[10000],num;
struct Edge{
    int next,to;
}edge[100000];
int stack[10000],top;
int color[10000],cnt;
int dfn[10000],low[10000];
int ID;
bool jd[10000];
int vis[10000];
inline void add(int from,int to){
    edge[++num]={head[from],to};
    head[from]=num;
}

void tarjan(int x){
    dfn[x]=++ID;
    low[x]=ID;
    jd[x]=1;
    stack[++top]=x;
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        if(!dfn[to]){
            tarjan(to);
            low[x]=min(low[x],low[to]);
        }
        else if(jd[to])    low[x]=min(low[x],dfn[to]);
    }
    if(dfn[x]==low[x]){
        jd[x]=0;
        color[x]=++cnt;
        while(stack[top]!=x){
            color[stack[top--]]=cnt;
            jd[stack[top+1]]=0;
            color[stack[top+1]]=cnt;
        }
        top--;
    }
    
}

int main(){
    int n;
    cin>>n;
    int x;
    for(int i=1;i<=n;++i){
        while(cin>>x&&x!=0){
            add(i,x);
        }
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i])    tarjan(i);
    }
    memset(jd,0,sizeof(jd));
    for(int i=1;i<=n;++i){
        for(int j=head[i];j;j=edge[j].next){
            if(color[i]!=color[edge[j].to]){
                jd[color[edge[j].to]]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;++i)    if(!jd[i])    ans++;
    cout<<ans<<endl;
    return 0;
}

 

Tarjan的强联通分量