tarjan（太监、塔扬、塔尖）算法

好吧，先说一下这个算法的名字问题，我真的无语了对于这个算法名字。

百度翻译是这样翻译的

（自己去看图片链接吧）我也很脑残，总之这个算法名字很奇怪就是了。这名字真多啊！废话不多说了，开始x生活。（好吧，上面的话都是ZHT写的）

（自己去看图片链接吧）我也很无奈，总之这个算法名字很奇怪就是了。这名字真多啊！废话不多说了。

算法思路

　　如果对原图进行深度优先搜索，由强连通分量定义可知，任何一个强连通分量是原图的dfs树的子树。那么，只要确定每个强连通分量子树的根，然后根据这些根从树的最底层开始，一个一个的取出强连通分量即可。那么剩下的问题就是如何确定强连通分量的根如何从最底层开始拿出强连通分量了。

　　对于确定强连通分量的根，在这里维护两个数组，一个是dfn[maxn]一个是low[maxn],其中dfn[v]表示顶点v被访问的时间，low[v]为顶点v邻接的未删除的顶点u的low[n]和low[v]的最小值（low[v]初始化为dfn[e]）。这样，在一次深度优先搜索的回溯过程中，如果发现low[v]的最小值（low[v]初始化为dfn[v]）。这样，在一次深度优先搜索的回溯过程中，如果发现low[v] == dfn[v]，那么当前顶点强连通分量的，而且他的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知low[v]一定被更改为一个比dfn[v]更小的值。

　　对于如何取出强连通分量，这个比较简单，如果当前节点为一个强连通分量的根，那么他的强联通分量一定是以该根为根节点的（剩下节点）子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。由于当前节点是这个强联通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并仍在堆栈中的节点都属于这个强连通分量。假设一个节点在当前节点压入堆栈以后压入并且还存在，同时不属于该强连通分量，那么一定属于另一个强连通分量，但当前节点是其根的祖宗，那么这个强连通分量应该在此之前已经被取出。

　　2.伪代码
　　（1）找一个没有被访问过的节点v;否则，算法结束。
　　（2）初始化dfn[v]和low[v]。
　　　　对于v所有的邻接顶点u；
　　　　①如果没有访问过，则转到步骤（2），同时维护low[v]。
　　　　②如果访问过，但没有删除，维护low[v]。
　　　　如果low[v] == dfn[v]，那么输出相应的强连通分量。

　　3.代码

 1 const int MAXN = 110;
 2 int m;
 3 struct node{
 4     int  t , next; 
 5 }Edge[MAXN + 10];
 6 
 7 int tarbfs(int k , int lay , int & scc_num){
 8     temp[k] = 1;
 9     low[k] = lay;
10     dfn[k] = lay;
11     stack[++m] = k;
12     for(int i = box[k] ; i != -1 ; i = Edge[i].next){
13         if(temp[Edge[i].t] == 0){
14             tarbfs(Edge[i].t , ++ lay , scc_num);
15         }
16         if(temp[Edge[i].t] == 1) low[k] = min(low[k] , low[Edge[i].t]);
17     }
18     if(dfn[k] == low[k]){
19         ++scc_num;
20         do{
21             low[stack[m]] == scc_num;
22             temp[stack[m]] = 2;
23         }while(stack[m--] != k);
24     }
25     return 0;
26 }
27 
28 int tarjan(int n){
29     int scc_num = 0 , lay = 1;
30     m = 0;
31     memset(temp , 0 , sizeof(temp));
32     memset(low  , 0 , sizeof(low)) ;
33     for(int i = 1 ; i <= n ; i ++){
34         if(temp[i] == 0)
35             tarbfs(i , lay , scc_num);
36     }
37     return scc_num;
38 }

tarjan

　　完事儿。

有个大佬说我的代码丑，于是我就co了一个好看的

 1 void tarjan(int u)
 2 {
 3     dfn[u] = low[u] = ++index;
 4     s.push(u);
 5     ins[u] = 1;
 6     int i, v;
 7     for(i = head[u]; i != -1; i = next[i])
 8     {
 9         v = to[i];
10         if(!dfn[v])
11         {
12             tarjan(v);
13             low[u] = std::min(low[u], low[v]);
14         }
15         else if(ins[v]) low[u] = std::min(low[u], dfn[v]);
16     }
17     if(low[u] == dfn[u])
18     {
19         size++;
20         do
21         {
22             v = s.top();
23             ins[v] = 0;
24             belong[v] = size;
25             s.pop();
26         }while(v != u);
27     }
28 }

好看的tarjan

　　完事儿。