【模板】强连通分量和tarjan算法

　　看了好久才终于明白了这个算法。。复杂度是O(n+m)。

　　我觉得这个算法不是很好理解，但是看懂了以后还是觉得听巧妙的。

　　下面给出模板代码和三组简单数据帮助理解。

　　代码如下：

 1 #include <stdio.h>
 2 #include <stack>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int N = 100+5;
 9 
10 stack<int> S;
11 int scc_cnt;  //强连通分量的个数
12 int dfs_clock;    //访问到该节点的时间戳
13 int belong[N];  //belong[i]表示i节点所属于第几个强连通分量
14 int dfn[N];     //表示第i个节点被访问的时间
15 int low[N];    //表示第i个节点的子节点所能访问到的最小的dfn值
16 vector<int> G[N];
17 
18 void dfs(int u)
19 {
20     dfn[u] = low[u] = ++dfs_clock;
21     S.push(u);
22     for(int i=0;i<G[u].size();i++)
23     {
24         int v = G[u][i];
25         if(!dfn[v])
26         {
27             dfs(v);
28             low[u] = min(low[u],low[v]);
29         }
30         else if(!belong[v]) //这句话等价于v在栈内
31         {
32             low[u] = min(low[u],low[v]);
33             //low[u] = min(low[u],dfn[v]);
34             //上面两种写法似乎都是没有问题的，但是如果仔细斟酌第三组数据和low的定义的话
35             //似乎是上面的写法更好，这里不敢确定，留个疑问。
36         }
37     }
38     if(low[u]==dfn[u])
39     {
40         scc_cnt++;
41         for(;;)
42         {
43             //因为元素x只有在出栈了以后才被赋予归属，所以这就是上面等价的原因
44             //同时，因为所有元素都有归属，则栈S中最后没有元素，因此不需要清空S
45             int x = S.top();S.pop();
46             belong[x] = scc_cnt;
47             if(x==u) break;
48         }
49     }
50 }
51 
52 void scc(int n)
53 {
54     memset(dfn,0,sizeof(dfn));
55     memset(belong,0,sizeof(belong));
56     dfs_clock = scc_cnt = 0;
57     for(int i=0;i<n;i++) //注意这里是0~n-1!
58     {
59         if(!dfn[i]) dfs(i);
60     }
61 }
62 
63 int main()
64 {
65     int n,m;
66     scanf("%d%d",&n,&m);
67     for(int i=0;i<m;i++)
68     {
69         int a,b;
70         scanf("%d%d",&a,&b);
71         G[a].push_back(b);
72     }
73     scc(n);
74     puts("");
75     for(int i=0;i<n;i++) printf("%d %d %d %d
",i,belong[i],dfn[i],low[i]);
76     printf("%d
",scc_cnt);
77     return 0;
78 }

　　三组数据如下：