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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define NUM_COLORS 50
typedef struct {
int c1, c2;
} bead;
bead *path;
int adj[NUM_COLORS][NUM_COLORS] = {{0}};
int path_counter = 0;
void find_path(int x, int y, int curr)
{
bead new_bead = {x, y};
path[path_counter++] = new_bead;
adj[x][y]-=1;
adj[y][x]-=1;
int new_x, new_y;
int found = 0;
switch (curr) {
case 0:
for (int i=0; i<NUM_COLORS && !found; i++) {
if (adj[x][i] >= 1) {
new_x = x; new_y = i;
found = 1;
}
}
break;
case 1:
for (int i=0; i<NUM_COLORS && !found; i++) {
if (adj[i][y] >= 1) {
new_x = i; new_y = y;
found = 1;
}
}
}
if (found==0)
return;
curr = (curr+1)%2;
find_path(new_x, new_y, curr);
return;
}
int main()
{
int tc, curr_tc = 0;
scanf("%d", &tc);
for (; curr_tc < tc; curr_tc++) {
int num_beads;
int start_x, start_y;
int color_count[50] = {0}, repeated_count[50] = {0};
scanf("%d", &num_beads);
path = malloc(sizeof(bead)*num_beads);
int a, b;
for (int x = 0; x < num_beads; x++) {
scanf("%d %d", &a, &b);
adj[a-1][b-1] += 1;
adj[b-1][a-1] += 1;
color_count[a-1] += 1;
color_count[b-1] += 1;
if (a == b) {
repeated_count[a-1] += 2;
}
if (x == 0) {
start_x = a-1;
start_y = b-1;
}
}
int possible = 1;
for (int x = 0; x < NUM_COLORS; x++) {
if (color_count[x] % 2 != 0) {
possible = 0;
break;
}
if (repeated_count[x] > 0 && color_count[x] < repeated_count[x]+2) {
possible = 0;
break;
}
}
printf("Case #%d\n", curr_tc+1);
if (!possible) {
printf("some beads may be lost\n");
}
else {
path_counter = 0;
find_path(start_y, start_x, 0);
printf("path counter: %d\n", path_counter);
for (int x = 0; x < path_counter; x++) {
if (x%2 != 0)
printf("%d %d\n", path[x].c1+1, path[x].c2+1);
else
printf("%d %d\n", path[x].c2+1, path[x].c1+1);
}
}
printf("\n");
for (int x=0; x < NUM_COLORS; x++) {
for (int y=0; y < NUM_COLORS; y++) {
adj[x][y] = 0;
adj[y][x] = 0;
}
}
free(path);
}
}
|
