首页 > 代码库 > hdu2460-Network：边的双连通分量
hdu2460-Network：边的双连通分量
题目大意：给出一个无向图以及Q次询问，每次询问增加一条无向边，要求输出增加这条边后剩余的桥的数目。
算法：类似于求割点的方法，先做一次dfs求出所有的桥，并且维护这棵dfs树，当一次询问加入一条边(a,b)之后，会在dfs上形成一个环，在这个环上的桥都变为非桥，这个环肯定经过a和b的LCA，此时我们只需在求LCA的过程中把经过的为桥的树边标记为非桥，同时cnt_bridge--再输出即可。
需要注意的是树边的编号是用树边指向的那个节点的编号来表示的，例如树边<u,v>用编号v表示。
还有就是加入一个#pragma预处理指令可以防止爆栈。
1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 #pragma comment(linker,"/STACk:10240000,10240000") 7 8 const int maxn = 100000 + 10; 9 int low[maxn],pre[maxn], iscut[maxn], dfs_clock=0; 10 bool isbridge[maxn]; 11 vector<int> G[maxn]; 12 int cnt_bridge; 13 int father[maxn]; 14 15 int dfs(int u, int fa) 16 { 17 father[u]=fa; 18 int lowu = pre[u] = ++dfs_clock; 19 int child = 0; 20 for(int i = 0; i < G[u].size(); i++) 21 { 22 int v = G[u][i]; 23 if(!pre[v]) // 没有访问过v 24 { 25 child++; 26 int lowv = dfs(v, u); 27 lowu = min(lowu, lowv); // 用后代的low函数更新自己 28 if(lowv > pre[u]) // 判断边(u,v)是否为桥 29 { 30 isbridge[v]=true; 31 cnt_bridge++; 32 } 33 } 34 else if(pre[v] < pre[u] && v != fa) 35 { 36 lowu = min(lowu, pre[v]); // 用反向边更新自己 37 } 38 } 39 if(fa < 0 && child == 1) 40 iscut[u] = 0; 41 return low[u]=lowu; 42 } 43 44 void init(int n) 45 { 46 memset(isbridge,false,sizeof isbridge); 47 memset(pre,0,sizeof pre); 48 cnt_bridge=dfs_clock=0; 49 for(int i=0; i<n; i++) 50 { 51 G[i].clear(); 52 } 53 } 54 55 void LCA(int a,int b) 56 { 57 while(pre[a]>pre[b]) 58 { 59 if(isbridge[a]) 60 { 61 isbridge[a]=false; 62 cnt_bridge--; 63 } 64 a=father[a]; 65 } 66 while(pre[b]>pre[a]) 67 { 68 if(isbridge[b]) 69 { 70 isbridge[b]=false; 71 cnt_bridge--; 72 } 73 b=father[b]; 74 } 75 if(a!=b) 76 { 77 while(pre[a]>pre[b]) 78 { 79 if(isbridge[a]) 80 { 81 isbridge[a]=false; 82 cnt_bridge--; 83 } 84 a=father[a]; 85 } 86 while(pre[b]>pre[a]) 87 { 88 if(isbridge[b]) 89 { 90 isbridge[b]=false; 91 cnt_bridge--; 92 } 93 b=father[b]; 94 } 95 } 96 } 97 98 int main() 99 {100 #ifndef ONLINE_JUDGE101 freopen("in.txt","r",stdin);102 #endif103 104 int n,m,Case=1;105 while(scanf("%d %d",&n,&m),!(n==0 && m==0))106 {107 init(n);108 for(int i=0; i<m; i++)109 {110 int a,b;111 scanf("%d %d",&a,&b);112 a--;113 b--;114 G[a].push_back(b);115 G[b].push_back(a);116 }117 118 // 第一次dfs找出所有的桥119 dfs(0,-1);120 int Q;121 cin>>Q;122 printf("Case %d:\n",Case++);123 while(Q--)124 {125 int a,b;126 scanf("%d %d",&a,&b);127 a--;128 b--;129 LCA(a,b);130 printf("%d\n",cnt_bridge);131 if(Q==0)132 printf("\n");133 }134 }135 136 return 0;137 }
hdu2460-Network：边的双连通分量
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。