题意:
给一个无向图..告诉哪些点之间有边相连..并且告诉边的标号..请输出任意一种欧拉回路边遍历的方案...
题解:
题目描述有问题..说是要输出字典序最小.又SJ...所以实际上只要是方案就行了...
由于题目保证了是连通图..所以不需要判连通性...那么先用度来判断该无向图是否存在欧拉回路...若存在..则任意一条路径出俩...方法是从任意一个点开始dfs...抽象的看就是把每一个环给拓展出来...最后倒过来输出...
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<queue> #include<stack> #include<set> #include<time.h> #include<map> #include<algorithm> #define ll long long #define eps 1e-5 #define oo 1000000007 #define pi acos(-1.0) #define MAXN 55 #define MAXM 2005 using namespace std; int s[MAXN][MAXM],d[MAXN],ans[MAXM],m,num; bool used[MAXM]; bool legal(int n) { for (int i=1;i<=n;i++) if (d[i]%2) return false; return true; } void dfs(int x) { for (int t=1;t<=m;t++) if (s[x][t] && !used[t]) { used[t]=true; dfs(s[x][t]); ans[++num]=t; } } int main() { int x,y,id,i; while (~scanf("%d%d",&x,&y) && x && y) { memset(d,0,sizeof(d)); memset(s,0,sizeof(s)); scanf("%d",&id); d[x]++,d[y]++; s[x][id]=y,s[y][id]=x; m=id; while (~scanf("%d%d",&x,&y) && x && y) { scanf("%d",&id); d[x]++,d[y]++; s[x][id]=y,s[y][id]=x; m=max(m,id); } if (!legal(50)) { printf("Round trip does not exist.\n"); continue; } memset(used,false,sizeof(used)),num=0; dfs(1); for (i=num;i>=1;i--) printf("%d ",ans[i]); printf("\n"); } return 0; }