图的强连通与缩点—Tarjan算法

先介绍几个基本概念：

1. 强连通： 在一个有向图G里，设两个点 a b，由a有一条路可以走到b，由b又有一条路可以走到a，我们就叫这两个顶点（a，b）强连通
2. 强连通图： 如果 在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图
3. 强连通分量：在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就叫这个子图叫做强连通分量

---

在Tarjan算法中，每个点被赋予以下两个信息：

·DFN值，即访问这个点的时间戳，每个点的DFN值都是唯一的

·LOW值，即这个点能访问到的最早的祖先节点，如果他不能向上访问，那么LOW值就是他自己

Tarjan算法的基本流程是：从一个点开始深搜，每一个点的的DFN值和LOW值初始化为时间戳，将其压栈，同时用布尔数组v来记录这个点有没有在栈里，假设这个点是x，压栈后开始查x的邻接点，假设邻接点是y，那么如果y没有被搜过（dfn[ y ]为0），就递归搜索y，然后如果搜完了y的low值更小，则更新x的low值，如果y搜过了且在栈里（v[ y ]为true），那么如果y的dfn值更小，则更新x的low值。做到此时，改写递归出口了，如果dfn[ x ]==low[ x ]，则说明他是一个强连通分量的入口，此时我们的ans++（找到了强连通分量1），弹出栈里x及他上面的点，标志着这个子图已经处理完毕*

我们在初始化时，将DFN数组全部置为0表示没有访问过，为了防止图不连通，主程序写成这样：

memset(dfn,0,sizeof(dfn));
memset(v,false,sizeof(v));//v数组用来跟踪是否在栈里
for(int i=1;i<=n;i++)
    if(!dfn[i]) tarjan(i);

现在可以写子程序了

void tarjan(int x)
{
   dfn[x]=low[x]=++tmmk;//time mark
   S.push(x);
   v[x]=true;
   for(int i=head[x];i;i=next[i])
   {
     int y=E[i].dot;
     if(!dfn[y])
     {
       tarjan(y);
       low[x]=min(low[x],low[y]);
     }
     else
       if(v[y])
          low[x]=min(low[x],dfn[y]);
   }
   if(dfn[x]==low[x])
   {
      ans++;
      int y;
      do{
        y=S.top();
        S.pop();
        v[y]=false;
        col[y]=ans;
        g[ans].push_back(y);
        /*
        这里处理了每个结果
        */
      }while(y!=x)
   }
}