zoj 2588 Burning Bridges(割边/桥)

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1588

题意：Ferry王国有n个岛，m座桥，每个岛都可以互达，现在要烧毁一些桥使得，但烧毁后每个岛仍可以互达，问哪些桥肯定不会被烧毁。

分析：给定一个无向连通图，要求图中的割边。注意，图中可能有重边，只要顶点u和v之间有重边，则这些重边任何一条都不可能是割边。这题的输出比较坑，pe了好多次。。。

AC代码:

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=+;

 const int M=+;

 struct EDGE{

     int v,id,next;

 }edge[M*];

 int first[N],low[N],dfn[N],bri[M];

 int g,cnt,top,ans;

 int min(int a,int b)

 {

     return a<b?a:b;

 }

 void AddEdge(int u,int v,int id)

 {

     edge[g].v=v;

     edge[g].id=id;

     edge[g].next=first[u];

     first[u]=g++;

 }

 void Tarjan(int u,int fa)

 {

     int i,v;

     low[u]=dfn[u]=++cnt;

     for(i=first[u];i!=-;i=edge[i].next)

     {

         v=edge[i].v;

         if(i==(fa^))

             continue;

         if(!dfn[v])

         {

             Tarjan(v,i);

             low[u]=min(low[u],low[v]);

             if(low[v]>dfn[u])

             {

                 bri[top++]=edge[i].id;

                 ans++;

             }

         }

         else

             low[u]=min(low[u],dfn[v]);

     }

 }

 int main()

 {

     int t,n,m,i,u,v;

     scanf("%d",&t);

     while(t--)

     {

         g=cnt=top=ans=;

         memset(first,-,sizeof(first));

         memset(low,,sizeof(low));

         memset(dfn,,sizeof(dfn));

         memset(bri,M,sizeof(bri));

         scanf("%d%d",&n,&m);

         for(i=;i<=m;i++)

         {

             scanf("%d%d",&u,&v);

             AddEdge(u,v,i);

             AddEdge(v,u,i);

         }

         for(i=;i<=n;i++)

             if(!dfn[i])

                 Tarjan(i,-);

         sort(bri,bri+top);

         printf("%d\n",ans);

         for(i=;i<top;i++)

         {

             printf("%d",bri[i]);

             if(i!=top-)

                 printf(" ");

         }

         if(top)

             printf("\n");

         if(t)

             printf("\n");

     }

     return ;

 }