学步园

题目大意：判断是否能组成欧拉回路。

思路：首先要判断图是否联通，再要判断全部是不是偶数点。如果满足以上两个，再用深搜去寻路径。题目要求要输出最小序列的。那么我们把遍按从小到大记录下来。然后搜的时候就从小到大搜，搜到以后就立即输出，得到的就是最小序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=1<<28;
struct node
{
    int s,e;
}map[2000];      //用该结构体记录边，s，e分别记录改边的两个端点

int MAX;
vector<int> path;    //用这个容器记录得到的路径
int vis[2000];
int v[50];
int set[50];  
int deg[50];  //深度
int home;
int find(int x)
{
    int r=x;
    while(r!=set[r])
        r=set[r];
    return r;
}

void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    else set[x]=y;
}



void dfs(int cur)
{
    int i;
    for(i=1;i<=MAX;i++)
	{
		if(!vis[i])continue;

		if(map[i].s==cur)   //如果找到一个端点  就继续深搜另外一个端点
		{
			vis[i]=0;
			dfs(map[i].e);
			path.push_back(i);
		}
		else if(map[i].e==cur)
		{
			vis[i]=0;
			dfs(map[i].s);
			path.push_back(i);
		}
	}
}


int main()
{
    int a,b,z;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        memset(deg,0,sizeof(deg));
		memset(vis,0,sizeof(vis));
		memset(v,0,sizeof(v));
		for(int i=0;i<45;i++)
			set[i]=i;
        for(int i=0;i<2000;i++)
            map[i].s=map[i].e=-1;
		path.clear();
		MAX=0;     //初始化
        if(!a && !b)break;
        home = a > b ? b : a;   
        scanf("%d",&z);
		MAX=max(MAX,z);
        map[z].e=a;
		map[z].s=b;
        deg[a]++;
        deg[b]++;
        v[a]=v[b]=1;
	vis[z]=1;     //记录边
        merge(a,b);
        while(scanf("%d%d",&a,&b)!=EOF)
        {
            if(!a && !b)break;
            scanf("%d",&z);
			MAX=max(MAX,z);
			map[z].e=a;
			map[z].s=b;
		    deg[a]++;
            deg[b]++;
            v[a]=v[b]=1;
			vis[z]=1;
            merge(a,b);
        }
        int num=0;
        int tem=0;
        for(int i=0;i<45;i++)
        {
            if(i==set[i] && v[i])tem++;
            if(deg[i]%2==1 && v[i])num++;
        }
     //   printf("max=========%d",MAX);
	//	printf("num===%d    tem====%d\n",num,tem);
        if(num!=0 || tem!=1){printf("Round trip does not exist.\n");continue;}   //判断
        else
        {
            dfs(home);
        }
        int i;
   //     printf("-----------------------");
        int first=1;
       // printf("size=====%d",path.size());
		for(i=path.size()-1;i>=0;i--)
        if(first) {printf("%d",path[i]);first=0;}
        else printf(" %d",path[i]);
        putchar(10);
    }
    return 0;
}