题目是中文的，我就不翻译了，也很好理解，就是一个A-B-C-A的一个循环的食物链，给定一些条件，问你哪些条件是错的
这一题，是一道比较经典的查并集的题目，那么这一题的思想是什么呢，对于给定的条件，x和y属于什么集合其实并没有给出，而且x和y之间还有其他的捕食的关系
但是我们现在假设，如果x和y都是属于同一类的，那么如果x属于A，那么y也一定属于A，那么也就是说，x和y属于同一个集合总是同时成立的的，再假设，如果x可以吃y，那么如果x属于A，那么y一定属于B,x属于B，那么y一定属于C或x属于C，那么y一定属于A，也就是说，在捕食关系中，y属于x的下一个集合一定成立的（A-B-C-A）
那么我们就可以用查并集来很好的维护这个关系，我们给x和y赋予A,B,C三个属性，并且用查并集来维护这些属性，如果x和y都属于一个集合，那么我们就要分别合并x和y的三个属性，如果属于不是关系，那么我们就把y的与x的下一个关系的集合进行合并，这三个属性可以用k，k+N，k+2*N的形式表现，这样就可以非常快速的维护关系了（因为对于找根的操作而言，查并集是最快的）
PS：查并集我用的是按大小合并的方式，本来这种方式可以有效的降低搜索的时间，但是因为这一题比较特殊（集合比较多）所以递归时间并没有减少很多，另外大家合并的时候一定要检查是不是同一个集合，不然会出错，并且MLE
另外这题，真是尼玛，有BUG，只能交单次数据（也就是不能while(~scanf())），真是个脑残bug
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 typedef int Position; 6 7 Position Find(Position); 8 void Union_Set(Position, Position); 9 int If_Same_Set(Position, Position); 10 11 static int *Set = NULL; 12 13 int main(void) 14 { 15 int N, case_sum, i; 16 int ans = 0, inform, x, y; 17 scanf("%d%d", &N, &case_sum); 18 Set = new int[3 * (N + 1)]; 19 for (i = 1; i <= 3 * N; i++) Set[i] = -1; 20 for (i = 0; i < case_sum; i++) 21 { 22 scanf("%d%d%d", &inform, &x, &y); 23 if (x > N || y > N)//如果在区域外，直接判断出错 24 { 25 ans++; 26 continue; 27 } 28 else if (inform == 1) 29 { 30 if (If_Same_Set(x, y + N) || If_Same_Set(x, y + 2 * N)) 31 //如果已经是捕食集合中,出错 32 ans++; 33 else//否则，则把xy的三个属性分别合并 34 { 35 Union_Set(x, y); 36 Union_Set(x + N, y + N); 37 Union_Set(x + 2 * N, y + 2 * N); 38 } 39 } 40 else if (inform == 2) 41 { 42 if (If_Same_Set(x, y) || If_Same_Set(x, y + 2 * N)) 43 //如果已经在非捕食集或已统一集合，出错 44 ans++; 45 else 46 { 47 Union_Set(x, y + N); 48 Union_Set(x + N, y + 2 * N); 49 Union_Set(x + 2 * N, y); 50 } 51 } 52 } 53 printf("%d\n", ans); 54 delete Set; 55 return 0; 56 } 57 58 Position Find(Position x) 59 { 60 //路径压缩 61 if (Set[x] < 0) 62 return x; 63 else 64 return Set[x] = Find(Set[x]); 65 } 66 67 int If_Same_Set(Position x, Position y) 68 { 69 return Find(x) == Find(y); 70 } 71 72 void Union_Set(Position x, Position y) 73 { 74 Position Rootx, Rooty; 75 Rootx = Find(x); 76 Rooty = Find(y); 77 78 if (Rootx != Rooty)//按大小求并，千万要注意不能是同一个集合的合并，不然会MLE 79 { 80 if (Set[Rootx] < Set[Rooty]) 81 { 82 Set[Rootx] += Set[Rooty]; 83 Set[Rooty] = Rootx; 84 } 85 else 86 { 87 Set[Rooty] += Set[Rootx]; 88 Set[Rootx] = Rooty; 89 } 90 } 91 }
原文：http://www.cnblogs.com/Philip-Tell-Truth/p/4850887.html