首页 > 其他 > 详细

双连通模板

时间:2016-07-29 21:27:03      阅读:124      评论:0      收藏:0      [点我收藏+]
 1 void dfs(int u,int fa)
 2 {
 3     dfn[u]=low[u]=++dfs_cut;
 4     vs[u]=1;
 5     s.push(u);
 6     int p=1;    ///去重
 7     for (int i=0;i<g[u].size();i++)
 8     {
 9         int v=g[u][i];
10         if (v==fa&&p)
11         {
12             p=0;
13             continue;
14         }
15         if (!vs[v])
16         {
17             dfs(v,u);
18             low[u]=min(low[u],low[v]);
19         }
20         else low[u]=min(low[u],dfn[v]);
21     }
22     
23     ///缩点
24     if (low[u]==dfn[u])
25     {
26         bcc_cut++;
27         int x;
28         while (1)
29         {
30             x=s.top();
31             s.pop();
32             bcc[x]=bcc_cut;
33             if (x==u) break;
34         }
35     }
36 }

 

双连通模板

原文:http://www.cnblogs.com/pblr/p/5719637.html

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