[USACO]EulerianTour (欧拉通路)

 1 /*
 2 ID: dream.y1
 3 PROG: fence
 4 LANG: C++
 5 */
 6 #include<stdio.h>
 7 #include<string.h>
 8 #include<stdlib.h>
 9 #include<time.h>
10 #include<math.h>
11 #include<limits.h>
12 int hs[2000];
13 int map[600][600];
14 int n;  
15    int be = 0; 
16    int en = 0;
17 int ans[1000];
18 int numans = 0 ; 
19 int okk = 0 ;
20 int is  = 0 ; 
21 void dfs(int k  )
22 {
23    if(!hs[k])
24    {
25       ans[numans] = k ; 
26       numans = numans +1;
27    }else {
28        while(hs[k])
29        {
30           for(int i = 1;i <= 500;i++)
31           {
32                if(map[k][i])
33                {
34                    map[k][i] -- ; 
35                    map[i][k] -- ; 
36                    hs[i] --; 
37                    hs[k] --;
38                    dfs(i);
39                }
40           }
41        }
42      ans[numans] = k ; 
43      numans ++ ; 
44    
45    }
46        
47 
48 }
49 int main(){
50 
51    freopen("fence.in","r",stdin);
52    freopen("fence.out","w",stdout);
53    memset(map,0,sizeof(map));
54    memset(hs,0,sizeof(hs));
55    scanf("%d",&n);
56    for(int i = 1;i  <= n;i ++)
57    {
58      int a, b; 
59      scanf("%d %d",&a,&b);
60      map[a][b] ++ ; 
61      map[b][a] ++ ; 
62      hs[a] ++ ; 
63      hs[b] ++ ; 
64    }
65    int ok = 0 ;
66    int bbe = INT_MAX ; 
67    for(int i = 1;i <= 500;i ++)
68    {
69       if(hs[i] % 2== 1)
70         {
71               is = 1; 
72             
73               be = i ; 
74               ok = 1;
75               break;
76         }
77       else if(hs[i])
78       {
79         bbe = bbe > i ? i:bbe; 
80       }
81    }
82    if(ok ) dfs(be);
83    if(!ok) 
84        dfs(bbe);
85    for(int i = numans -1 ;i  >= 0 ; i --)
86        printf("%d\n",ans[i]);
87 return 0 ;
88 }