首页 > 代码库 > ZOJ 1588 Burning Bridges (tarjan求割边)
ZOJ 1588 Burning Bridges (tarjan求割边)
题目链接
题意 ： N个点M条边，允许有重边，让你求出割边的数目以及每条割边的编号（编号是输入顺序从1到M）。
思路 ：tarjan求割边，对于除重边以为中生成树的边（u，v），若满足dfn[u] < low[v]，则边（u，v）是割边。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct node 9 {10 int u ;11 int v;12 int next ;13 int num ;14 }p[200100];15 int dfn[200100],low[200100] ;//dfn深度优先遍历生成树的顺序，low表示该节点能够到达的祖先的最小编号16 int bridge[200100] ,nbrid,vis[200010];//桥的编号，割边的条数，vis表示该点是否访问过17 int cnt,head[200100],tot ;18 19 void Init()20 {21 cnt = nbrid = tot= 0 ;22 memset(head,-1,sizeof(head)) ;23 memset(vis,0,sizeof(vis)) ;24 }25 void addedge(int u,int v,int id)26 {27 //p[cnt].u = u ;28 p[cnt].v = v ;29 p[cnt].num = id ;30 p[cnt].next = head[u] ;31 head[u] = cnt ++ ;32 //p[cnt].u = v ;33 p[cnt].v = u ;34 p[cnt].num = id ;35 p[cnt].next = head[v] ;36 head[v] = cnt ++ ;37 }38 39 void DFS(int u,int fu)40 {41 dfn[u] = low[u] = tot++ ;42 vis[u] = 1 ;43 for(int i = head[u] ; i != -1 ; i = p[i].next)44 {45 int v = p[i].v;46 if(p[i].num != fu && vis[v] )47 {48 low[u] = min(low[u],dfn[v]) ;49 }50 else if( !vis[v] )51 {52 DFS(v,p[i].num) ;53 low[u] = min(low[u],low[v]) ;54 if(low[v] > dfn[u])55 {56 bridge[++nbrid] = p[i].num;57 }58 }59 }60 }61 int main()62 {63 int T ,N,M,u,v;64 scanf("%d",&T) ;65 while(T--)66 {67 Init() ;68 scanf("%d %d",&N,&M) ;69 for(int i = 1 ; i <= M ; i++)70 {71 scanf("%d %d",&u,&v) ;72 addedge(u,v,i) ;73 }74 DFS(1,-1) ;75 sort(bridge+1,bridge+1+nbrid) ;76 printf("%d\n",nbrid) ;77 for(int i = 1 ; i <= nbrid ; i++)78 {79 if(i != nbrid)80 printf("%d ",bridge[i]) ;81 else printf("%d\n",bridge[i]) ;82 }83 if(T)puts("") ;84 }85 return 0;86 }
鹏哥说我那样写的太丑了，非给我改成下边的样子
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct node 9 {10 int u ;11 int v;12 int next ;13 int num ;14 }p[200100];15 int dfn[200100],low[200100] ;16 int bridge[200100] ,nbrid,vis[200010];17 int cnt,head[200100],tot ;18 int fb[200100];19 void Init()20 {21 cnt = nbrid = tot= 0 ;22 memset(head,-1,sizeof(head)) ;23 memset(vis,0,sizeof(vis)) ;24 memset(fb,0,sizeof(fb));25 memset(dfn,0,sizeof(dfn));26 memset(low,0,sizeof(low));27 }28 void addedge(int u,int v,int id)29 {30 //p[cnt].u = u ;31 p[cnt].v = v ;32 p[cnt].num = id ;33 p[cnt].next = head[u] ;34 head[u] = cnt ++ ;35 //p[cnt].u = v ;36 p[cnt].v = u ;37 p[cnt].num = id ;38 p[cnt].next = head[v] ;39 head[v] = cnt ++ ;40 }41 void DFS(int u)42 {43 dfn[u] = low[u] = ++tot;44 //vis[u] = 1 ;45 for(int i = head[u] ; i != -1 ; i = p[i].next)46 {47 int v=p[i].v;48 if(fb[i^1])continue;49 fb[i]=1;50 if(dfn[v] )//如果该点没被访问过dfn自然为0，所以不用vis数组也可51 {52 low[u] = min(low[u],dfn[v]) ;53 }54 else55 {56 DFS(v) ;57 low[u] = min(low[u],low[v]) ;58 if(low[v] > dfn[u])59 {60 bridge[++nbrid] = p[i].num;61 }62 }63 }64 }65 int main()66 {67 int T ,N,M,u,v;68 scanf("%d",&T) ;69 while(T--)70 {71 Init() ;72 scanf("%d %d",&N,&M) ;73 for(int i = 1 ; i <= M ; i++)74 {75 scanf("%d %d",&u,&v) ;76 addedge(u,v,i) ;77 }78 DFS(1) ;79 sort(bridge+1,bridge+1+nbrid) ;80 printf("%d\n",nbrid) ;81 for(int i = 1 ; i <= nbrid ; i++)82 {83 if(i != nbrid)84 printf("%d ",bridge[i]) ;85 else printf("%d\n",bridge[i]) ;86 }87 if(T)puts("") ;88 }89 return 0;90 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。