首页 > 代码库 > ZOJ2588：Burning Bridges（无向连通图求割边）
ZOJ2588：Burning Bridges（无向连通图求割边）
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1588
吐下槽，不得不说ZOJ好坑，模版题做了一个多小时。
题意：
* 给出一个无向图，输入n(表示n个定点，1~n), m(m条边，有重边)，
* (2 <= N <= 10 000, 1 <= M <= 100 000)，求这个无向图中的桥，
* 并输出桥属于输入中边的id.
之前学图的连通性因为没看懂双连通分量，就把连通性的这些知识点搁置了，一直没有刷这方面的题，由于之前已经弄懂求桥的算法，所以看到题就直接上了，结果被一些
小错误给击败了，还好算法的思想没出问题，贴一下代码，以后当模版用。求桥：low[v]>dfn[u](u,v)为树枝边。
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <stack>#define N 10010using namespace std;struct node{ int x,y,w,next,flag;} eg[20*N];int tt,head[N],dfn[N],low[N],ti,n,m,top;int f[20*N];void init(){ tt=0; ti=1; top=0; memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(f,false,sizeof(f));}void add(int xx,int yy,int nu){ for(int i=head[xx]; i!=-1; i=eg[i].next)//去重 { if(eg[i].y==yy) { eg[i].flag=1; return ; } } eg[tt].x=xx; eg[tt].y=yy; eg[tt].w=nu; eg[tt].flag=0; eg[tt].next=head[xx]; head[xx]=tt++;}void tarjan(int u,int fa){ dfn[u]=low[u]=ti++; for(int i=head[u]; i!=-1; i=eg[i].next) { int v=eg[i].y; if(v==fa) continue; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]&&!eg[i].flag) { f[top++]=eg[i].w; } } else //无向图没有横跨边 { low[u]=min(dfn[v],low[u]); } }}int main(){ int T,xx,yy; scanf("%d",&T); while(T--) { init(); scanf("%d %d",&n,&m); for(int i=1; i<=m; i++) { scanf("%d %d",&xx,&yy); add(xx,yy,i); add(yy,xx,i); } tarjan(1,-1); int sum=0; for(int i=1; i<=m; i++) { if(f[i]) sum++; } printf("%d\n",top); if(top) { sort(f,f+top); for(int i=0; i<top-1; i++) { printf("%d ",f[i]); } printf("%d\n",f[top-1]); } if(T!=0) printf("\n"); } return 0;}//无向图是没有横边的
我不知道为什么这么写就PE
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <stack>#define N 10010using namespace std;struct node{ int x,y,w,next,flag;}eg[20*N];int tt,head[N],dfn[N],low[N],ti,n,m;bool f[20*N];void init(){ tt=0; ti=1; memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(f,false,sizeof(f));}void add(int xx,int yy,int nu){ for(int i=head[xx];i!=-1;i=eg[i].next) { if(eg[i].y==yy) { eg[i].flag=1; return ; } } eg[tt].x=xx; eg[tt].y=yy; eg[tt].w=nu; eg[tt].flag=0; eg[tt].next=head[xx]; head[xx]=tt++;}void tarjan(int u,int fa){ dfn[u]=low[u]=ti++; for(int i=head[u];i!=-1;i=eg[i].next) { int v=eg[i].y; if(v==fa) continue; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]&&!eg[i].flag) { f[eg[i].w]=true; } } else //无向图没有横跨边 { low[u]=min(dfn[v],low[u]); } }}int main(){ int T,xx,yy; scanf("%d",&T); while(T--) { init(); scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d %d",&xx,&yy); add(xx,yy,i); add(yy,xx,i); } tarjan(1,-1); int sum=0; for(int i=1;i<=m;i++) { if(f[i]) sum++; } printf("%d\n",sum); int F=1; for(int i=1;i<=m;i++) { if(f[i]) { if(F) { printf("%d",i); F=0; } else printf(" %d",i); } } printf("\n"); if(T!=0) printf("\n"); } return 0;}//无向图是没有横边的
ZOJ2588：Burning Bridges（无向连通图求割边）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。