题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1272
第二条并查集，和畅通工程的解法类似。判断小希的迷宫不符合条件，即有回路。我的做法是，在合并两个集合的时候，当fx = fy，即有共同祖先的时候，说明就有回路。
这题有三点要注意：1、格式问题。题目说的“每两组数据之间有一个空行。”是会PE的！！实际上输出Yes或No之后加多个\n即可，不需要再画蛇添足再输多一个换行。 2、 当整数对列表只有0 0 时，要输出Yes 3、当不相交的集合个数>=2时，也是不符合条件的，要输出No
1 #include <iostream> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 6 const int maxn = 100000 + 5; 7 int set[maxn], flag[maxn]; 8 int sign; 9 10 int find_set(int x) 11 { 12 while (x != set[x]) 13 x = set[x]; 14 return x; 15 } 16 17 void union_set(int x, int y) 18 { 19 int fx = find_set(x); 20 // printf("fx = %d\n", fx); 21 int fy = find_set(y); 22 // printf("fy = %d\n", fy); 23 if (fx != fy) 24 { 25 set[fx] = fy; 26 // printf("set[%d] = %d\n", fx, set[fx]); 27 } 28 else 29 sign = 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 = sign = 0; 38 while (scanf("%d%d", &a, &b) && (a != -1 || b != -1)) 39 { 40 if (i == 0 && a == 0 && b == 0) // i = 0代表列表中的数据是第一组 41 { 42 printf("Yes\n"); 43 } 44 else if (a != 0 && b != 0) 45 { 46 i++; 47 if (!flag[a] && set[a] != a) // flag的作用是输入数据时当存在多个相同的数据时，保证只需要存入一次set[a]，起到类似监视哨的作用 48 { 49 set[a] = a; 50 flag[a] = 1; 51 // printf("set[%d] = %d\n", a, set[a]); 52 } 53 if (!flag[b] && set[b] != b) 54 { 55 set[b] = b; 56 flag[b] = 1; 57 // printf("set[%d] = %d\n", b, set[b]); 58 } 59 if (a > b) 60 swap(a, b); // 保证小的数指向的祖先比它大,其实这个判断不要也行
61 union_set(a, b); // 合并a、b元素，使a、b成为一个集合 62 } 63 else 64 { 65 for (cnt = 0, j = 1; j < maxn; j++) 66 if (set[j] == j) // 统计不相交集合个数 67 cnt++; 68 if (cnt > 1) // 不相交集合个数超过1个 69 sign = 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 = sign = 0; 77 } 78 } 79 return 0; 80 }