Tarjan强连通分量详解

1、简介：

在阅读下列内容之前，请务必了解 图论相关概念 中的基础部分。

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

这里要介绍的是如何来求强连通分量。

 

 

2、引入：

在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：

 

 

 

3、算法思想：

求强连通分量就相当于求环(或类似于环可以一遍又一遍无限走下去，切走不出这个环)的个数。

其他人博客上说什么：树边（tree edge），横叉边（cross edge），反祖边（back edge），前向边（forward edge），这些太复杂了，对像我一样的蒟蒻不友好以下是一段简洁的解释。

先说算法步骤：

1、我们要对一张图(有向图)进行遍历。

       记录：dfn[x]:   存x点的时间戳（是第几个遍历这个点的），（相当于记录了遍历的顺序）；

                  low[x]:   存x点最早能访问到的时间戳。

2、思考：若dfn[x]=low[x]，就说明x点无论怎么走，都无法到达时间戳更靠前的点，证明x点是一个环的开始（环顶）。

3、将遍历到的点依次入栈，当判断到环顶时，栈中的点就是一个强连通分量。

 

 

4、详细步骤：

• 一个结点的子树内结点的 dfn 都大于该结点的 dfn。
• 从根开始的一条路径上的 dfn 严格递增，low 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点  和与其相邻的结点 （ 不是  的父节点）考虑 3 种情况：

1.  v未被访问：继续对 v 进行深度搜索。在回溯过程中，用 low[v] 更新 。因为存在从 u 到 v 的直接路径，所以说 v 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。
2.  v被访问过，已经在栈中：根据 low 值的定义，用 dfn[v] 或low[v] 更新 low[u] 。
3.  v被访问过，已不在栈中：说明v已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

 

 

5、例题：（洛谷 P2863 [USACO06JAN] The Cow Prom S）

        

//洛谷 P2863 [USACO06JAN] The Cow Prom S 
#include
using namespace std;
const int N=2e4+2,M=5e4+2;
int n,m,dfn[N],low[N],first[N],stk[N],siz[N],top=0,tot=0,cnt=0,ans=0;
bool in[N];
struct node{int v,ne;}e[M];
void add(int u,int v){
    e[++tot]={v,first[u]};
    first[u]=tot;
}
void tarjan(int u){       //tarjan算法求强连通分量
    dfn[u]=low[u]=++tot;
    in[u]=1;       //表示u点在栈中 
    stk[++top]=u;  //将u记入栈中 
    for(int i=first[u];i;i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);  //更新low[u]值的意义是让u点不提前出栈 
        }
        else if(in[v]) low[u]=min(low[u],low[v]);
    }
    if(low[u]==dfn[u]){
        int y;
        ++cnt;
        do{
            y=stk[top--];in[y]=0;
            siz[cnt]++;
        }while(u!=y);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        add(u,v);          //建单向边 
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);  //图有可能不连通，存在几个分开的图 
    for(int i=1;i<=cnt;++i) if(siz[i]>1) ans++;   //siz[]记录每一个强连通分量的大小 
    printf("%d",ans);
    return 0;
}

 

 

6、后继知识

学了tarjan强连通分量，就可以学习缩点等，真正涉及到应用的东西。