学步园

题目链接:   zoj 2588

题目大意:   在无向连通图中找桥，并且按序号输出

解题思路:   Tarjan查找割边

                  数据中可能会出现重边，需要判断是否是重边

                  每次加入新的边，则枚举此顶点之前加入的边中是否存在另一点

                  low[vv]>dnf[u]是桥，low[vv]>=dnf[u]是割点

代码:

//Final  Tarjan 找桥(割边)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define MAX 10005
#define MIN(a,b) a<b?a:b
struct snode{
	int to,next,num,m;
}edge[MAX*20];
int visit[MAX],low[MAX],dnf[MAX],pre[MAX],ans[MAX],ansn,Index,n,high;

void Add_edge(int a,int b,int mm)
{
	int i;
	for(i=pre[a];i!=-1;i=edge[i].next)  //遍历一遍之前加入该点的所有边
	{
		if(edge[i].to==b)
			break;
	}
	if(edge[i].to==b)    //记录重边，重边不是桥
		edge[i].num++;
	else
	{
		edge[Index].to=b;
		edge[Index].m=mm;
		edge[Index].num=1;
		edge[Index].next=pre[a];
		pre[a]=Index++;
	}
}

void Tarjan(int u,int father)
{
	int v,vv;
	for(v=pre[u];v!=-1;v=edge[v].next)
	{
		vv=edge[v].to;
		if(!visit[vv])
		{
			low[vv]=dnf[vv]=++high;
			visit[vv]=1;
			Tarjan(vv,u);
			low[u]=MIN(low[u],low[vv]);
			if(low[vv]>dnf[u]&&edge[v].num==1)  //low[vv]>dnf[u]是桥,low[vv]>=dnf[u]是割点
			{
				ans[ansn++]=edge[v].m;
			}
		}
		else if(vv!=father)                //**
		{
			low[u]=MIN(low[u],dnf[vv]);
		}
	}
}

int main()
{
	int m,i,t,a,b;
	scanf("%d",&t);
	while(t--)
	{
		Index=0;
		memset(pre,-1,sizeof(pre));
		memset(visit,0,sizeof(visit));
		memset(edge,0,sizeof(edge));
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			Add_edge(a,b,i+1);
			Add_edge(b,a,i+1);
		}
		low[1]=dnf[1]=visit[1]=high=1;  //初始化
		ansn=0;
		Tarjan(1,-1);
		sort(ans,ans+ansn);             //序号排序输出
		printf("%d\n",ansn);
		for(i=0;i<ansn-1;i++)
		{
			printf("%d ",ans[i]);
		}
		if(ansn)
	    	printf("%d\n",ans[ansn-1]);
		if(t)
			puts("");
	}
	return 0;
}