Posted on 2009-05-20 10:45
superman 阅读(165)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <stack>
2 #include <iostream>
3
4 using namespace std;
5
6 int n = 1024, m;
7 int deg[1024];
8 int map[1024][1024];
9
10 stack<int> ans_st;
11
12 void search(int p)
13 {
14 for (int i = 0; i < n; i++)
15 if (map[p][i])
16 {
17 map[p][i]--, map[i][p]--;
18 search(i);
19 }
20 ans_st.push(p + 1);
21 }
22
23 int main()
24 {
25 freopen("fence.in", "r", stdin);
26 freopen("fence.out", "w", stdout);
27
28 cin >> m;
29
30 int s, t;
31 for (int i = 0; i < m; i++)
32 {
33 cin >> s >> t;
34 deg[s - 1]++; deg[t - 1]++;
35 map[s - 1][t - 1]++; map[t - 1][s - 1]++;
36 }
37
38 int i;
39 for (i = 0; i < n; i++)
40 if (deg[i] % 2 == 1)
41 {
42 search(i);
43 break;
44 }
45 if (i == n)
46 for (int j = 0; j < n; j++)
47 if (deg[j])
48 {
49 search(j);
50 break;
51 }
52
53 while (ans_st.empty() == false)
54 {
55 cout << ans_st.top() << endl;
56 ans_st.pop();
57 }
58
59 return 0;
60 }
61