学步园

题目链接:   hdu
3849

题目大意:   给出无向图，找出所有的割边

                  并且按边输入的顺序输出

                  如果图不连通则直接输出0

解题思路:   先用map或者Hash把字符串转化为编号

                  根据编号建立无向图

                  Tarjan搜索无向图的桥

                  判断Tarjan的深度，小于n说明是不连通图

代码:

//Final   Tarjan搜索桥
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
#define MAX 10005
#define MIN(a,b) a<b?a:b
struct snode{
	int to,next,num;
}edge[MAX*20];
char ZM[MAX*10][16];
char ZM2[MAX*10][16];
char ch1[MAX],ch2[MAX];
int visit[MAX],low[MAX],dnf[MAX],pre[MAX],ans[MAX*10],Index,high,kk;

void Add_edge(int a,int b,int m)
{
	edge[Index].num=m;
	edge[Index].to=b;
	edge[Index].next=pre[a];
	pre[a]=Index++;
	return ;
}

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])
		{
			visit[vv]=1;
			low[vv]=dnf[vv]=++high;
            Tarjan(vv,u);
            low[u]=MIN(low[u],low[vv]);
            if(low[vv]>dnf[u])               //low[vv]>dnf[u]就是桥
            {
			 	ans[kk++]=edge[v].num;
            }
		}
        else if(vv!=father)                  //**
        {
            low[u]=MIN(low[u],dnf[vv]);
            
        }
	}
}

int main()
{
    
	int n,m,i,k,t,a,b;
	scanf("%d",&t);
	while(t--)
	{
        map<string,int> HashZS;
		Index=kk=0;
		memset(pre,-1,sizeof(pre));
		memset(dnf,0,sizeof(dnf));
		memset(visit,0,sizeof(visit));
		scanf("%d%d",&n,&m);
		for(i=0,k=0;i<m;i++)
		{
			scanf("%s%s",ch1,ch2);
			if(HashZS[ch1]==0)       //map把字符串转换成编号
			{
				HashZS[ch1]=++k;
			}
			if(HashZS[ch2]==0)       //map把字符串转换成编号
			{
				HashZS[ch2]=++k;
			}
			strcpy(ZM[i],ch1);
			strcpy(ZM2[i],ch2);
			a=HashZS[ch1];
			b=HashZS[ch2];
			Add_edge(a,b,i);
			Add_edge(b,a,i);
		}
		low[1]=dnf[1]=visit[1]=high=1;
		Tarjan(1,-1);
		if(high!=n)                  //如果Tarjan的深度小于n则说明图不连通
		{
			printf("0\n");
			continue;
		}
        sort(ans,ans+kk);            //根据边输入的顺序排序
		printf("%d\n",kk);
		for(i=0;i<kk;i++)
		{
			printf("%s %s\n",ZM[ans[i]],ZM2[ans[i]]);
		}
	}
	return 0;
}