1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <cstdio>#include <cstdlib>#include <list>#include <vector>#include <stack>#define N 45using namespace std;int degree[N], adj_matrix[N][N];stack<int> s;int round_exist(){ for (int i=1; i< N; i++) { if (degree[i]%2 != 0) return 0; } return 1;}void init(){ for (int i=1; i< N; i++){ degree[i] = 0; for (int j=1; j< N; j++) adj_matrix[i][j] = 0; }}void find_circuit(int u){ if (degree[u]==0){ s.push(u); return; } for (int v=1; v< N; v++) { if (adj_matrix[u][v]>0){ adj_matrix[u][v]--; degree[u]--, degree[v]--; find_circuit(v); } } s.push(u);}int main(){ int x, y; while (true){ scanf("%d %d", &x, &y); if (x==0) break; init(); while (true){ adj_matrix[x][y] = 1; degree[x]++, degree[y]++; scanf("%d %d", &x, &y); if (x==0) break; } if (!round_exist()) printf("Circuit does not exist.\n\n"); else find_circuit(1); /*從1開始走*/ printf("%d", s.top()); s.pop(); while (!s.empty()) { printf(" -> %d", s.top()); s.pop(); } } return 0;} |
範例輸入輸出：
input:
1 2
1 3
2 1
2 5
3 2
3 4
4 5
5 1
5 3
0 0
output:
1 -> 2 -> 1 -> 3 -> 2 -> 5 -> 3 -> 4 -> 5 -> 1
