POJ1182 食物链 并查集（最简单的版本）
|
并查集可以说是数据结构里比较简单的一种了，这一道题我看了很多人的题解 大致有两种做法: 1.建立一个3*n大小的数组，将这些动物放在这三个范围里面n,2*n,3*n，然后进行判断和合并 2.利用“向量”的思想/将同类，被捕食，捕食设置为0，1，2然后进行关系的改变 kuangbin的做法： http://www.cnblogs.com/kuangbin/archive/2013/04/02/2996358.html 最简单的应该是第一种 1 //方法1 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdio> 6 using namespace std; 7 const int N=5e4+10; 8 int n,k,d,x,y,ans; 9 int f[N*3+1]; //r=relative;f=father 10 void init(){ 11 for (int i = 1; i <= n*3;i++) 12 f[i] = i; 13 }//开一个3*n的father数组，也就是f[]； 14 int find(int x){ 15 return f[x] == x ? x : f[x] = find(f[x]); 16 } 17 bool issame(int a,int b){ 18 return find(a) == find(b); 19 } 20 void unionset(int x,int y){ 21 x = find(x),y = find(y); 22 if(x==y) 23 return; 24 f[y] = x; 25 } 26 int main(){ 27 //IOS 28 scanf("%d%d",&n,&k); 29 init(); 30 while(k--){ 31 scanf("%d%d%d",&d,&x,&y); 32 if(x>n||y>n||y<=0||x<=0||(d!=1&&d!=2)){ 33 ans++; 34 continue; 35 } 36 if(d==1){ 37 if(issame(x,y+n)||issame(x+n,y)) 38 ans++; 39 else 40 unionset(x,y),unionset(x + n,y + n),unionset(x + 2 * n,y + 2 * n);//这样合并的意思是：如果x为A类，则y也为A类；如果x为B类，y也为B类；C类同理，但现在并没有确定谁是哪一类 41 }//只是说明，不管x，y属于哪一类，他们两个都是在同一类里面，是共祖的 42 if(d==2){ 43 if(issame(x,y)||issame(x,y+2*n)) 44 ans++; 45 else 46 unionset(x,y + 2 * n),unionset(x + 2 * n,y);//这样合并的意思就是，仍然不管x属于哪个种类，但是x一定要处于y的食物链上端1级 47 48 } 49 cout << ans; 50 //system("pause"); 51 return 0; 52 } ? 所以我们进行的一系列的合并或者是捕食关系的设置，都是将这些动物的相对位置进行改变， 如果两个动物都还没有被设置过，或者只有一个动物被设置过，那么第37行/第43行的条件就不会成立，所以不用担心会有冲突的情况 ? 那么，需不需要再判断issame(x+n,y+2*n)这一类的条件，是否需要把每个情况都列举出来？ 这个是不用的，因为只要两个都没被设置过，或者是只有一个被设置过，那么可以直接进入unionset环节，也就是第40行或者第46行， 40：unionset(x,unionset(x + 2 * n,y + 2 * n);
46：unionset(x,y + 2 * n),unionset(x + 2 * n,y);
这两行的操作兼顾了所有的情况，也就是： 假如x属于A，那么y应该是______； 假如x属于B，那么y应该是______； 假如x属于C，那么y应该是______； ? 这样，x与y的相对位置始终是确定的； 判断的时候也就不会出错 ? 我看到有好几个这种方法的题解里面，都有人用了一个rk[n*3]数组，但这个数组删去，同样可以AC，这个rank数组的作用是判断捕食关系，但其实这个数组是不需要的， 因为题设里面已经说明，当d==2的时候，需要判断是否是x捕食y，那么只需要利用issame函数判断是否是y捕食x，如果是，则谎言数量+1，如果不是，进入unionset环节，进行相对位置的改变 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
