首页 > 其他 > 详细

ACM模板——强连通分量

时间:2019-09-17 19:12:44      阅读:64      评论:0      收藏:0      [点我收藏+]
技术分享图片
 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

 

ACM模板——强连通分量

原文:https://www.cnblogs.com/Asurudo/p/11536005.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!