首页 > 代码库 > Gym - 100712H Bridges（边—双连通分量）
Gym - 100712H Bridges（边—双连通分量）
https://vjudge.net/problem/Gym-100712H
题意：
给出一个图，求添加一条边后最少的桥数量。
思路：
参考了ZSQ大神的题解http://blog.csdn.net/v5zsq/article/details/61922051
很明显的边—双连通的题目，首先缩点建新图。然后寻找树中的最大直径，这样就能将桥的数量减至最小。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack> 10 using namespace std; 11 12 const int maxn=100000+5; 13 14 struct Edge 15 { 16 int to,next; 17 bool flag;//标记是否是桥 18 }edge[maxn*2]; 19 20 stack<int> S; 21 int n,m; 22 int head[maxn],tot; 23 int low[maxn],dfn[maxn],belong[maxn]; 24 int index,top; 25 int block;//边双连通块数 26 bool instack[maxn]; 27 int bridge;//桥的数目 28 int e[maxn][2]; 29 int deep; //最长直径 30 int pos; //最长直径端点 31 32 void addedge(int u,int v) 33 { 34 edge[tot].to=v,edge[tot].next=head[u],edge[tot].flag=0; 35 head[u]=tot++; 36 } 37 38 void Tarjan(int u,int pre) 39 { 40 int v; 41 low[u]=dfn[u]=++index; 42 S.push(u); 43 instack[u]=1; 44 for(int i=head[u];~i;i=edge[i].next) 45 { 46 v=edge[i].to; 47 if(v==pre)continue; 48 if(!dfn[v]) 49 { 50 Tarjan(v,u); 51 if(low[u]>low[v])low[u]=low[v]; 52 if(low[v]>dfn[u]) 53 { 54 bridge++; 55 edge[i].flag=1; 56 edge[i^1].flag=1; 57 } 58 } 59 else if(instack[v]&&low[u]>dfn[v]) 60 low[u]=dfn[v]; 61 } 62 if(low[u]==dfn[u]) 63 { 64 block++; 65 do 66 { 67 v=S.top(); S.pop(); 68 instack[v]=0; 69 belong[v]=block; 70 } 71 while(v!=u); 72 } 73 } 74 75 void init() 76 { 77 memset(dfn,0,sizeof(dfn)); 78 index=block=top=bridge=tot=0; 79 memset(head,-1,sizeof(head)); 80 } 81 82 //邻接表寻找树的直径 83 void dfs(int u,int fa,int cnt) 84 { 85 if(cnt>deep) {deep=cnt;pos=u;} 86 for(int i=head[u];~i;i=edge[i].next) 87 { 88 int v=edge[i].to; 89 if(v!=fa) dfs(v,u,cnt+1); 90 } 91 } 92 93 int main() 94 { 95 //freopen("D:\\input.txt","r",stdin); 96 int T; 97 scanf("%d",&T); 98 while(T--) 99 {100 scanf("%d%d",&n,&m);101 init();102 for(int i=1;i<=m;i++)103 {104 scanf("%d%d",&e[i][0],&e[i][1]);105 addedge(e[i][0],e[i][1]);106 addedge(e[i][1],e[i][0]);107 }108 Tarjan(1,1);109 110 //缩点，重建图111 tot=0;112 memset(head,-1,sizeof(head));113 int ans=0;114 for(int i=1;i<=m;i++)115 {116 int u=belong[e[i][0]], v=belong[e[i][1]];117 if(u!=v)118 {119 ans++;120 addedge(u,v);121 addedge(v,u);122 }123 }124 125 deep=0;126 dfs(1,1,0);127 deep=0;128 dfs(pos,pos,0);129 printf("%d\n",ans-deep);130 }131 return 0;132 }
Gym - 100712H Bridges（边—双连通分量）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。