首页 > 代码库 > HDU 2460 Network（桥+LCA）
HDU 2460 Network（桥+LCA）
http://acm.hdu.edu.cn/showproblem.php?pid=2460
题意：
给出图，求每次增加一条边后图中桥的数量。
思路：
先用tarjan算法找出图中所有的桥，如果lowv>pre[u]，那么u—v就是桥，此时可以标记一下v。
之后就是利用LCA，找到两个节点的公共祖先，在这条路径上的桥就不再是桥了。（此时就相当于这些桥组成的树，可以在脑海中缩点）
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=100000+5; 17 18 int n, m; 19 int tot; 20 int cnt; 21 int head[maxn]; 22 int dfs_clock; 23 int pre[maxn]; 24 int low[maxn]; 25 int isbridge[maxn]; 26 int p[maxn]; 27 28 struct node 29 { 30 int v; 31 int next; 32 }e[400000+5]; 33 34 void addEdge(int u, int v) 35 { 36 e[tot].v=v; 37 e[tot].next=head[u]; 38 head[u]=tot++; 39 } 40 41 void init() 42 { 43 cnt=0; 44 dfs_clock=0; 45 memset(pre,0,sizeof(pre)); 46 memset(isbridge,0,sizeof(isbridge)); 47 for(int i=1;i<=n;i++) p[i]=i; 48 } 49 50 int dfs(int u, int fa) 51 { 52 int lowu=pre[u]=++dfs_clock; 53 for(int i=head[u];i!=-1;i=e[i].next) 54 { 55 int v=e[i].v; 56 if(!pre[v]) 57 { 58 p[v]=u; 59 int lowv=dfs(v,u); 60 lowu=min(lowu,lowv); 61 if(lowv>pre[u]) {cnt++;isbridge[v]=1;} 62 } 63 else if(pre[v]<pre[u] && v!=fa) 64 lowu=min(lowu,pre[v]); 65 } 66 return low[u]=lowu; 67 } 68 69 int LCA(int u, int v) 70 { 71 while(low[u]>low[v]) 72 { 73 if(isbridge[u]) {cnt--;isbridge[u]=0;} 74 u=p[u]; 75 } 76 while(low[v]>low[u]) 77 { 78 if(isbridge[v]) {cnt--;isbridge[v]=0;} 79 v=p[v]; 80 } 81 while(u!=v) 82 { 83 if(isbridge[u]) {cnt--;isbridge[u]=0;} 84 if(isbridge[v]) {cnt--;isbridge[v]=0;} 85 u=p[u]; 86 v=p[v]; 87 } 88 } 89 90 int main() 91 { 92 //freopen("in.txt","r",stdin); 93 int kase=0; 94 while(~scanf("%d%d",&n,&m)) 95 { 96 if(n==0 && m==0) break; 97 tot=0; 98 memset(head,-1,sizeof(head)); 99 while(m--)100 {101 int u,v;102 scanf("%d%d",&u,&v);103 addEdge(u,v);104 addEdge(v,u);105 }106 init();107 dfs(1,-1);108 int q;109 scanf("%d",&q);110 printf("Case %d:\n",++kase);111 while(q--)112 {113 int u,v;114 scanf("%d%d",&u,&v);115 LCA(u,v);116 printf("%d\n",cnt);117 }118 printf("\n");119 }120 return 0;121 }
HDU 2460 Network（桥+LCA）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。