2039 骑马修栅栏

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define N 2010
 5 int map[N][N];  //两两之间的关系 
 6 int du[N];  //度数 
 7 int ans[N],now;  
 8 int n,m,begn,maxn=0;
 9 void dfs(int a)  
10 {
11     for(int i=1;i<=maxn;++i)  
12     {
13         if(map[a][i]>0)
14         {
15             map[a][i]--;
16             map[i][a]--;
17             dfs(i);
18         }
19     }
20     ans[++now]=a;
21 } 
22 int main()
23 {
24     cin>>m;
25     for(int i = 1;i <= m;++i)
26     {
27         int x,y;
28         scanf("%d%d",&x,&y);
29         map[x][y]++;
30         map[y][x]++;
31         du[x]++;
32         du[y]++; 
33         maxn=max(maxn,max(x,y));
34     }
35     for(int i=1;i<=maxn;++i)  //找到奇数度的点作为起点 
36     {
37         if(du[i]%2==1)
38         {
39             begn=i;break;
40         }
41     }
42     if(!begn)  //若没有找最小的点 
43     {
44         for(int i=1;i<=maxn;++i)
45             if(du[i]>0)
46             {
47                 begn=i;break;
48             }
49     }
50     dfs(begn); //搜索 
51     for(int i=now;i>=1;--i)
52     {
53         printf("%d\n",ans[i]);
54     }
55     return 0;
56 }