题目：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 10010 using 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,0,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 ",top); if(top) { sort(f,f+top); for(int i=0; i<top-1; i++) { printf("%d ",f[i]); } printf("%d ",f[top-1]); } if(T!=0) printf(" "); } return 0; } //无向图是没有横边的
我不知道为什么这么写就PE
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <stack> #define N 10010 using 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 ",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(" "); if(T!=0) printf(" "); } return 0; } //无向图是没有横边的