强连通分量

概念

1.连通：在有向图中，若存在点a到达点b的有向路径并且存在点b到达点a的有向路径，则点a和点b是（强）连通的。
2.强连通图：如果有向图G中的任意两点都是强连通的，则图G为强连通图，如图2。
3.强连通分量：有向图G中最大的强连通子图为其强连通分量。例如，图一中，{A,B,C}和{D}就是图一的两个强连通分量。

强连通分量

Tarjan算法

  Tarjan算法是基于DFS搜索的是时间复杂度为O（n）的计算强连通分量的算法。

• 原理

  在图G中若点A，B是强连通的则以AB之间的有向路径构成一个环路，以其上任一点为C起点进行DFS搜索必定会找到起点C。Tarjan算法就是通过一个数组LOW来记录环路的起点，在环路中的每个顶点都是该强连通分量的一部分。

• 具体步骤

  首先需要定义两个全局数组LOW和DFN，其中DFN记录当前节点DFS的标号，LOW记录当前节点DFS所能到达的最小的的节点标号。还要定义一个全局栈STACK用来保存正在处理的节点。
  选定一个初始节点s，利用Tarjan求强连通分量。将该点的编号设为1,此时LOW[s]=DFN[s]=1，并将该点压栈;然后，遍历其相临节点，递归调用Tarjan算法。比较每次调用Tarjan算法DFN[i]的值比DFN[i-1]的值大一。遍历完子节点后LOW值更新为子节点中LOW最小的节点的LOW值。
然后弹栈直到LOW等于DFN，弹出的元素处于同一连通分量中。

• 代码

//hdu-1269 迷宫城堡
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
const  int  MAX_N=10100;
vector<int> G[MAX_N];
int isStack[MAX_N];
int dfn[MAX_N],low[MAX_N],vis[MAX_N],color[MAX_N];
int d_num=0;
int now=1;
int ans=0;
int n,m;
stack <int> stk;
void tarjan(int s){
    dfn[s]=low[s]=++d_num;
    vis[s]=1;
    stk.push(s);
    isStack[s]=1;
    for(int i=0;i<G[s].size();i++){
        if(!vis[G[s][i]]){
            tarjan(G[s][i]);
            low[s]=min(low[s],low[G[s][i]]);
         }
          else{
              if(isStack[G[s][i]])
                  low[s]=min(low[s],low[G[s][i]]);
          }
    }
    if(low[s]!=dfn[s])
        return;
    int tmp=stk.top();
    stk.pop();
    while(low[tmp]!=dfn[tmp]){
        isStack[tmp]=0;
        color[tmp]=now;
        tmp=stk.top();
        stk.pop();
    }
    color[tmp]=now;
    now++;
    return;
}
int main(){
    while(scanf("%d%d",&n,&m)){
        if(n==0)
            break;
        ans=0;
        d_num=0;
        now=1;
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        memset(color,0,sizeof(color));
        memset(low,0,sizeof(low));
        memset(isStack,0,sizeof(isStack);
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
        }
        tarjan(1);
        for(int i=1;i<=n;i++){
            if(color[i]==1)
                ans++;
        }
        if(n==ans)
            printf("Yes\n");
        else
            printf("No\n");
        for(int i=0;i<=n;i++){
            G[i].clear();
        }
    }
    return 0;
}