ACM模板——强连通分量

 1 vector<int> G[maxn];
 2 vector<int> rG[maxn];
 3 vector<int> vs;
 4 vector<int> ans[maxn];
 5 bool used[maxn];
 6 int V,E;
 7 int rnt = 0;
 8 void add_edge(int from,int to)
 9 {
10     G[from].pb(to);
11     rG[to].pb(from);
12 }
13 void dfs(int v)
14 {
15     used[v] = true;
16     _for(i,0,G[v].size())
17         if(!used[G[v][i]])
18             dfs(G[v][i]);
19     vs.pb(v);
20 }
21 void rdfs(int v,int k)
22 {
23     used[v] = true;
24     ans[k].pb(v);
25     _for(i,0,rG[v].size())
26         if(!used[rG[v][i]])
27             rdfs(rG[v][i],k);
28 }
29 //第k个集合里有哪些节点 ans[k]
30 //rnt为最大集合的集合大小
31 void Kosaraju()
32 {
33     memset(used,0,sizeof(used));
34     _for(v,1,V+1)
35         if(!used[v])
36             dfs(v);
37     
38     memset(used,0,sizeof(used));
39     int k = 0;
40     _rep(i,vs.size()-1,-1)
41         if(!used[vs[i]])
42         {
43             rdfs(vs[i],k);
44             rnt = max(rnt,(int)ans[k].size());
45             k ++;
46         }
47 }

Kosaraju

 1 int N,M;
 2 int ver[maxn],Next[maxn],head[maxn],dfn[maxn],low[maxn];
 3 int Gver[maxn],GNext[maxn],Ghead[maxn],Gtot;
 4 int stack[maxn],ins[maxn],c[maxn];
 5 vector<int> scc[maxn];
 6 int tot,top,cnt,nm;
 7 //cnt个强连通分量，scc[i]记录编号为i的强连通分量中的所有节点，c[x]表示x所在连通分量地区
 8 void addori(int x,int y)
 9 {
10     ver[++tot] = y,Next[tot] = head[x],head[x] = tot;
11 }
12 void tarjan(int x)
13 {
14     dfn[x] = low[x] = ++nm;
15     stack[++top] = x,ins[x] = 1;
16     for(int i = head[x]; i; i = Next[i])
17     {
18         int y = ver[i];
19         if(!dfn[y])
20         {
21             tarjan(y);
22             low[x] = min(low[x],low[y]);
23         }
24         else if(ins[y])
25             low[x] = min(low[x],dfn[y]);
26     }
27     if(dfn[x] == low[x])
28     {
29         cnt ++;
30         int y;
31         do
32         {
33             y = stack[top --],ins[y] = 0;
34             c[y] = cnt,scc[cnt].pb(y);
35         }
36         while(x != y);
37     }
38 }
39 void addAft(int x,int y)
40 {
41     Gver[++Gtot] = y;
42     GNext[Gtot] = Ghead[x];
43     Ghead[x] = Gtot;
44 }
45 void Shrink()
46 {
47     _for(i,1,N+1)
48     if(!dfn[i])
49         tarjan(i);
50 
51     _for(x,1,N+1)
52     for(int i = head[x]; i; i = Next[i])
53     {
54         int y = ver[i];
55         if(c[x]==c[y]) continue;
56         addAft(c[y],c[x]);
57     }
58 }

Tarjan 缩点