hdu1272小希的迷宫解题报告

1 #include
2 #include
3 #include <string.h>
4 using namespace std;
5
6 const int maxn &＃61; 100000 &＃43; 5;
7 int set[maxn], flag[maxn];
8 int sign;
9
10 int find_set(int x)
11 {
12 while (x !&＃61; set[x])
13 x &＃61; set[x];
14 return x;
15 }
16
17 void union_set(int x, int y)
18 {
19 int fx &＃61; find_set(x);
20 // printf("fx &＃61; %d\n", fx);
21 int fy &＃61; find_set(y);
22 // printf("fy &＃61; %d\n", fy);
23 if (fx !&＃61; fy)
24 {
25 set[fx] &＃61; fy;
26 // printf("set[%d] &＃61; %d\n", fx, set[fx]);
27 }
28 else
29 sign &＃61; 1;
30 }
31
32 int main()
33 {
34 int a, b, i, j, cnt;
35 memset(set, 0, sizeof(set));
36 memset(flag, 0, sizeof(flag));
37 i &＃61; sign &＃61; 0;
38 while (scanf("%d%d", &a, &b) && (a !&＃61; -1 || b !&＃61; -1))
39 {
40 if (i &＃61;&＃61; 0 && a &＃61;&＃61; 0 && b &＃61;&＃61; 0) // i &＃61; 0代表列表中的数据是第一组
41 {
42 printf("Yes\n");
43 }
44 else if (a !&＃61; 0 && b !&＃61; 0)
45 {
46 i&＃43;&＃43;;
47 if (!flag[a] && set[a] !&＃61; a) // flag的作用是输入数据时当存在多个相同的数据时&＃xff0c;保证只需要存入一次set[a]&＃xff0c;起到类似监视哨的作用
48 {
49 set[a] &＃61; a;
50 flag[a] &＃61; 1;
51 // printf("set[%d] &＃61; %d\n", a, set[a]);
52 }
53 if (!flag[b] && set[b] !&＃61; b)
54 {
55 set[b] &＃61; b;
56 flag[b] &＃61; 1;
57 // printf("set[%d] &＃61; %d\n", b, set[b]);
58 }
59 if (a > b)
60 swap(a, b); // 保证小的数指向的祖先比它大,其实这个判断不要也行
61 union_set(a, b); // 合并a、b元素&＃xff0c;使a、b成为一个集合
62 }
63 else
64 {
65 for (cnt &＃61; 0, j &＃61; 1; j )
66 if (set[j] &＃61;&＃61; j) // 统计不相交集合个数
67 cnt&＃43;&＃43;;
68 if (cnt > 1) // 不相交集合个数超过1个
69 sign &＃61; 1;
70 if (sign)
71 printf("No\n");
72 else
73 printf("Yes\n");
74 memset(set, 0, sizeof(set));
75 memset(flag, 0, sizeof(flag));
76 i &＃61; sign &＃61; 0;
77 }
78 }
79 return 0;
80 }