强连通分量(Tarjan)

有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

介绍如下：

http://baike.baidu.com/link?url=ywmRd_qHWhHfefP-fquUv2Zr8W7jEf3gE-KJVaNgf2sdrFIA755uVWMJFL43hx9jYqtvMoUFYHYX1Zzj_KBdGa

原理可以参考这几篇文章：

http://blog.csdn.net/shiqi_614/article/details/7833628

（这一篇不是专门讲tarjan算法的，但却是讲得最清晰的。。所以放在第一个）

http://blog.csdn.net/xinghongduo/article/details/6195337

http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591370.html

在这里坑了好久，原来判断强连通分量low不一定要统一，只要判断出栈就行了

当然要统一也行，我在注释里写了

实现如下：

  1 #include <iostream>
  2 #include <vector>
  3 #include <stack>
  4 using namespace std;
  5 
  6 #define MIN(a,b) ((a)<(b)?(a):(b))
  7 
  8 stack<int> sta;// 存储已遍历的结点
  9 vector<int> gra[100];// 邻接表表示图
 10 int dfn[100];// dfs访问次序
 11 int low[100];// 能追溯到的最早的根
 12 bool insta[100];// 检查是否在栈中
 13 vector<int> Component[100];// 获得强连通分量结果
 14 int InComponent[100];// 记录每个点在第几号强连通分量里
 15 int index,CNumber;// 索引号，强连通分量个数
 16 int n,m;//vex,edge
 17 
 18 void init()
 19 {
 20           for(int i = 1;i<=n;i++)
 21           {
 22                     dfn[i] = 0;
 23                     low[i] = 0;
 24                     insta[i] = false;
 25                     gra[i].clear();
 26                     Component[i].clear();
 27           }
 28 
 29           index = CNumber = 0;
 30 
 31           while(!sta.empty())
 32                     sta.pop();
 33 }
 34 
 35 void tarjan(int u)
 36 {
 37           insta[u] = true;
 38           low[u] = dfn[u] = ++index;
 39           sta.push(u);
 40 
 41           for(int i = 0;i<gra[u].size();i++)
 42           {
 43                     int v = gra[u][i];//点ｕ的邻接点
 44                     cout<<"b"<<v<<endl;
 45                     if(dfn[v]==0)
 46                     {
 47                               tarjan(v);
 48                               low[u] = MIN(low[u],low[v]);
 49                     }
 50                     else if(insta[v] && dfn[v]<low[u])
 51                     {
 52                               low[u] = dfn[v];
 53 
 54                               //这是我自己加的，如果要统一low[]值的话就要这个
 55                               //也就是说，low值不是一定要统一的
 56                               if(low[u]>low[v])
 57                                         low[u] = low[v];
 58 
 59                     }
 60           }
 61 
 62           if(low[u]==dfn[u])
 63           {
 64                     ++CNumber;
 65                     while(!sta.empty())
 66                     {
 67                               int j = sta.top();
 68                               cout<<j<<" ";
 69                               sta.pop();
 70                               Component[CNumber].push_back(j);
 71                               InComponent[j]=CNumber;
 72                               insta[j] = false;
 73                               if(j==u)
 74                                         break;
 75                     }
 76                     cout<<endl;
 77           }
 78 }
 79 
 80 void input()
 81 {
 82           for(int i = 1;i<=m;i++)
 83           {
 84                     int a,b;
 85                     cin>>a>>b;
 86                     gra[a].push_back(b);
 87           }
 88 }
 89 
 90 int main()
 91 {
 92           cin>>n>>m;
 93           init();
 94           input();
 95           tarjan(1);
 96 }
 97 /*
 98 6 8
 99 1 2
100 1 3
101 2 4
102 3 4
103 3 5
104 4 1
105 4 6
106 5 6
107 */
108 /*
109 8 13
110 1 3
111 2 1
112 2 4
113 3 2
114 3 4
115 3 5
116 4 6
117 5 6
118 5 7
119 6 4
120 6 8
121 7 5
122 7 8
123 */
124 /*
125 8 13
126 1 3
127 2 1
128 2 4
129 3 2
130 3 5
131 4 3
132 4 6
133 5 6
134 5 7
135 6 4
136 6 8
137 7 5
138 7 8
139 */
140 /*
141 4 5
142 1 2
143 1 4
144 2 3
145 3 1
146 4 3
147 
148 
149 */