题目链接: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 ;
}