首页 > 代码库 > poj 1182 食物链（种类并查集 ‘初心者’）
poj 1182 食物链（种类并查集 ‘初心者’）
题目链接：http://poj.org/problem?id=1182
借着这题可以好好理解一下种类并查集，这题比较简单但挺经典的。
题意就不解释了，中问题。
关于种类并查集结局方法也是挺多的
1扩增倍数。
就是有几种关系就建立几倍数组，具体方法在这里不详细说了，这种方法有弊端
比较复杂而且内存消耗比较大如果关系比较多就容易爆掉。
2向量的方法。
这种方法要详细解说一下。这个方法好处都有啥.......(自行脑补后面的话）
这个方法的优点占用内存比较小而且比较简洁。只要找到关系就行。
下面就用方法2来说一下这道题目
这题总共有3种关系
1）同类。2）A eat B。3）B eat A。
所以就设root[i]，等于1表示同类，等于2表示关系2，等于3表示关系3
初始化是将root的值全定义为0表示他们毫不相关，然后再慢慢将关系加入进去
int find(int x) {
if(x == f[x])
return x;
int t = find(f[x]);
root[x] = (root[x] + root[f[x]]) % 3;//这个注意一下在寻找根节点的过程中要记得更新一下root的值。
f[x] = t;
return f[x];
}//寻找根节点
int a = find(x) , b = find(y);
if(d == 1) {
if(a == b) {
if(root[x] != root[y])//这个很好理解就不解释了
count++;
}
else {
f[a] = b;
root[a] = root[y] - root[x];//root[a]+root[x]=root[y] 这样就好理解了吧
root[a] = (root[a] + 3) % 3;
}
}
if(d == 2) {
if(a == b) {
if((root[x] + 1) % 3 != root[y])//这个也很好理解就是A->B or B->C or C->A他们的root关系就差1
count++;
}
else {
f[a] = b;
root[a] = root[y] - root[x] - 1;//root[a]+root[x] +1 = root[y];
root[a] = (root[a] + 3) % 3;
}
}
//这些都是关键代码
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 5e4 + 10;int n , k , root[M] , f[M];void init() { for(int i = 1 ; i <= n ; i++) { f[i] = i , root[i] = 0; }}int find(int x) { if(x == f[x]) return x; int t = find(f[x]); root[x] = (root[x] + root[f[x]]) % 3; f[x] = t; return f[x];}int main() { int d , x , y; scanf("%d%d" , &n , &k); int count = 0; init(); while(k--) { scanf("%d%d%d" , &d , &x , &y); if(x > n || y > n) { count++; continue; } int a = find(x) , b = find(y); if(d == 1) { if(a == b) { if(root[x] != root[y]) count++; } else { f[a] = b; root[a] = root[y] - root[x]; root[a] = (root[a] + 3) % 3; } } if(d == 2) { if(a == b) { if((root[x] + 1) % 3 != root[y]) count++; } else { f[a] = b; root[a] = root[y] - root[x] - 1; root[a] = (root[a] + 3) % 3; } } } printf("%d\n" , count); return 0;}poj 1182 食物链（种类并查集 ‘初心者’）