题目链接: poj 1041
题目大意: 给出无向图,每条边有唯一的序号
是否存在欧拉回路,若存在输出边序号最小字典序的路径
解题思路: 无向欧拉回路的判断方法,若存在奇数度点,则不存在欧拉回路
依据静态邻接链表的特性,从序号大到小建立边
因为这样总能保证序号最小的边首先访问到
PS:欧拉路径的问题要记得判断图是否联通
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> 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.c<b.c)?1:0; } void Add_edge(int a,int b,int c) { edge[Index].to=b; edge[Index].w=c; edge[Index].next=pre[a]; pre[a]=Index++; } void Fleury(int start) { int i,v; for(i=pre[start];i!=-1;i=edge[i].next) { v=edge[i].to; if(!visit[edge[i].w]) { visit[edge[i].w]=1; Fleury(v); answer[++kk]=edge[i].w; //记录边的访问顺序 } } } int main() { int i,k,a1,a2,a3,pd,start; while(scanf("%d%d",&a1,&a2)!=EOF) { k=1,Index=kk=pd=0; if(a1==0&&a2==0) break; memset(visit,0,sizeof(visit)); memset(ans,0,sizeof(ans)); memset(pre,-1,sizeof(pre)); memset(Du,0,sizeof(Du)); scanf("%d",&a3); ans[k].a=a1,ans[k].b=a2,ans[k].c=a3; Du[a1]++,Du[a2]++; if(a1>a2) 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(a1<S) S=a1;if(a2<S) S=a2; if(a1>E) 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; }