poj 1041 John's trip (邊最小字典序歐拉路徑 Fleury)

題目鏈接: poj 1041

題目大意: 給出無向圖，每條邊有唯一的序號

是否存在歐拉回路，若存在輸出邊序號最小字典序的路徑

解題思路: 無向歐拉回路的判斷方法，若存在奇數度點，則不存在歐拉回路

依據靜態鄰接鏈表的特性，從序號大到小建立邊

因為這樣總能保證序號最小的邊首先訪問到

PS:歐拉路徑的問題要記得判斷圖是否聯通

代碼:

#include 
#include 
#include 
#include 
using namespace std;
#define MAX	2010
#define INF 0x3f3f3f3f
int S,E,n,Index,pre[MAX],visit[MAX],Du[MAX],kk,answer[MAX];
struct snode{
	int w,pd,to,next;
}edge[MAX<<3];
struct node{
	int a,b,c;
}ans[MAX<<3];

bool cmp(struct node a,struct node b)
{
	return (a.ca2)
            S=a2,E=a1;
        else
            S=a1,E=a2;
		while(1)
		{
			scanf("%d%d",&a1,&a2);
			if(a1==0&&a2==0)
				break;
			scanf("%d",&a3);
			if(a1E) E=a1;if(a2>E) E=a2;
			Du[a1]++,Du[a2]++;
			ans[++k].a=a1,ans[k].b=a2,ans[k].c=a3;
		}
		start=S;
		for(i=S;i<=E;i++)
		{
			if(Du[i]==0)
				continue;
			if(Du[i]%2==1)   //有奇數度點則不存在歐拉回路
			{
				pd=1;break;
			}
		}
		if(pd==1)
		{
			printf("Round trip does not exist.\n");
			continue;
		}
        sort(ans+1,ans+1+k,cmp);
		for(i=k;i>=1;i--)
		{
			Add_edge(ans[i].a,ans[i].b,ans[i].c);
			Add_edge(ans[i].b,ans[i].a,ans[i].c);
		}
		Fleury(start);
		for(i=kk;i>=1;i--)
			printf("%d%c",answer[i],(i==1)?'\n':' ');
	}
	return 0;
}