题目是中文的,我就不翻译了,也很好理解,就是一个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