首页 > 代码库 > POJ 3352 Road Construction（边—双连通分量）
POJ 3352 Road Construction（边—双连通分量）
http://poj.org/problem?id=3352
题意：
给出一个图，求最少要加多少条边，能把该图变成边—双连通。
思路：
双连通分量是没有桥的，dfs一遍，计算出每个结点的low值，如果相等，说明属于同一个双连通分量。
接下来把连通分量缩点，然后把这些点连边。
对于一棵无向树,我们要使得其变成边双连通图,需要添加的边数 == (树中度数为1的点的个数+1)/2。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 12 const int maxn=50000+5; 13 14 int n,m; 15 int pre[maxn],isbridge[maxn],bccno[maxn],bcc_cnt,dfs_clock; 16 int low[maxn]; //low[i]表示i结点及其后代能通过反向边连回的最早的祖先的pre值 17 int degree[maxn]; 18 vector<int> G[maxn],bcc[maxn]; 19 20 int tarjan(int u,int fa) 21 { 22 int lowu=pre[u]=++dfs_clock; 23 for(int i=0;i<G[u].size();i++) 24 { 25 int v=G[u][i]; 26 if(!pre[v]) 27 { 28 int lowv=tarjan(v,u); 29 lowu=min(lowu,lowv); 30 /* 31 if(lowv>pre[u]) 32 isbridge[G[u][i]]=isbridge[G[u][i]^1]=1; //桥 33 */ 34 } 35 else if(pre[v]<pre[u] && v!=fa) 36 lowu=min(lowu,pre[v]); 37 } 38 return low[u]=lowu; 39 } 40 41 /* 42 void dfs(int u) 43 { 44 pre[u]=1; 45 bccno[u]=bcc_cnt; 46 for(int i=0;i<G[u].size();i++) 47 { 48 int v=G[u][i]; 49 if(isbridge[v]) continue; 50 if(!pre[v]) dfs(v); 51 } 52 } 53 */ 54 55 /* 56 void find_ebbc() 57 { 58 bcc_cnt=dfs_clock=0; 59 memset(pre,0,sizeof(pre)); 60 memset(isbridge,0,sizeof(isbridge)); 61 memset(bcc,0,sizeof(bcc)); 62 memset(bccno,0,sizeof(bccno)); 63 for(int i=1;i<=n;i++) 64 if(!pre[i]) tarjan(i,-1); 65 66 memset(pre,0,sizeof(pre)); 67 for(int i=1;i<=n;i++) //计算边—双连通分量 68 if(!pre[i]) 69 { 70 bcc_cnt++; 71 dfs(i); 72 } 73 } 74 */ 75 76 int main() 77 { 78 //freopen("D:\\input.txt","r",stdin); 79 while(~scanf("%d%d",&n,&m) && n && m) 80 { 81 for(int i=1;i<=n;i++) G[i].clear(); 82 for(int i=0;i<m;i++) 83 { 84 int u,v; 85 scanf("%d%d",&u,&v); 86 G[u].push_back(v); 87 G[v].push_back(u); 88 } 89 //find_ebbc(); 90 tarjan(1,-1); 91 for(int i=1;i<=n;i++) 92 { 93 for(int j=0;j<G[i].size();j++) 94 { 95 int v=G[i][j]; 96 if(low[i]!=low[v]) 97 degree[low[v]]++; 98 } 99 }100 int cnt=0;101 for(int i=1;i<=n;i++)102 if(degree[i]==1) cnt++;103 printf("%d\n",(cnt+1)/2);104 }105 return 0;106 }
POJ 3352 Road Construction（边—双连通分量）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。