有向图的强连通分量

这篇具有很好参考价值的文章主要介绍了有向图的强连通分量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有向图的强连通分量

对于一个有向图，连通分量：对于分量中任意两点u,v，必然可以从u走到v,且从v走到u.
强连通分量：极大连通分量。
求出强连通分量后，可以通过将强连通分量缩点的方式，将有向图转化成有向无环图。
求强连通分量的方法：tarjan O(n+m),时间复杂度是线性的
1 . 采用dfs来遍历整个图，可以将边分为四类（x->y）

树枝边 x是y的父节点
前向边 x是y的祖先，x可以到达y
后向边 y是x的祖先, x可以到达y
横叉边 x可以到达已经遍历且已经回溯过的y点

2 .如何确定点在连通分量中

存在一条后向边，使其指向祖先节点
存在一条横插边，走过了横叉边，又存在一条后向边指向原来的点的祖先节点

3 .引入一个时间戳的概念

dfn[u] 表示遍历到u的时间,也就是dfs序
low[u] 表示从u所在强连通分量中，所能遍历到的层次最高的点的dfs序。
当dfs[u]==low[u]时，表示u是其所在的强连通分量的最高点

4 . 对于tarjan算法,我的理解是每次都是对以当前的点为根节点的子图进行操作的，遍历完子图中的所有点时，如果dfs[u]==low[u]表示当前的根就是在强连通图中，一个一个清掉栈中的元素，在没有清掉当前点的时候，清理出的元素都是强连通图中的元素。


int n,m;
int h[N],ne[M],e[N],idx=0;
int dfn[N],low[N],tm=0;
int vis[N];
int id[N],cnt=0,ids[N];
int dout[N];
stack<int> s;

void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
  dfn[u]=low[u]=++tm;
  s.push(u);
  vis[u]=1;
  for(int i=h[u];~i;i=ne[i])
  {
     int j=e[i];
     if(!dfn[j])
     { 
           tarjan(j);
           low[u]=min(low[u],low[j]);
     }
     else if(vis[j]) low[u]=min(low[u],dfn[j]);
  }

   if(dfn[u]==low[u])
   {
    ++cnt;
    int y;
    do{
       y=s.top();
       s.pop();
       vis[y]=0;
       id[y]=cnt;
       ids[cnt]++;
    }while(y!=u);
   }
}