POJ 1182 食物链

• 三维关系并查集
• 数据大了不能cin
• 为什么是三维? 其实相当于映射关系，且维护在一个数组中
• 首先肯定想着是并查集合并一个动物类A B C,但是怎么表示猎物和天敌的关系呢？
• 我想着用另一个数组表示捕猎的关系a吃b->eat[a]=b，但是发现不知道如何维护，
• 这里我们开2个数组来维护 捕猎 和 天敌的关系,仍然用并查集来维护，
• 为了方便，我们将它压缩到一个数组中i表自身,i+n表猎物,i+2*n表天敌，i+n 和 i+2*n相当于映射到了一个新的值，但是不会重复,从pre[n]开到pre[3*n]

  #include <iostream>
  using namespace std;
  const int maxn = 2e5;
  int pre[maxn];
  int n,k;
  int ans=0;
  int find(int x) {
  	if (x == pre[x]) return x;
  	return pre[x] = find(pre[x]); 
  }
  void merge(int a,int b) {
  	int ra = find(a);
  	int rb = find(b);
  	//如果ra == rb 再复制一次
  	pre[ra] = rb;
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	scanf("%d%d",&n,&k);
  	for (int i=1; i<=3*n; i++) pre[i] = i;
  	while (k--) {
  		int ch,a,b;
  //		cin >> ch >> a >> b;
  		scanf("%d%d%d",&ch,&a,&b);
  		if (a>n || b>n) {
  			ans++;
  			continue;
  		} 
  		if (ch == 1) { // a,b是同类
  			//首先判断天敌之间的关系
  			if (find(a+n)==find(b) || find(a+2*n)==find(b)) {
  				ans++;
  				continue;
  			}
  			merge(a,b);
  			merge(a+n,b+n);
  			merge(a+2*n,b+2*n);
  		}
  		else {
  			//输入的是 u 吃 v
  			if (a == b) {
  				ans++;
  				continue;
  			}
  			if (find(a) == find(b) || find(a+2*n)==find(b)) {
  				ans++;
  				continue;
  			}
  			merge(a+n,b); //u的猎物和v合并
  			merge(a,b+2*n); //u和v的天敌合并
  			merge(a+2*n,b+n); //u的天敌和v的猎物合并
  			//满足三元关系
  		}
  	}
  	printf("%d",ans);
  	return 0;
  }

  关于种类并查集一点想法：

1. 食物链有三种种类，种子那题有2中种类，
2. 两种种类时，可以通过加权并查集来解决
3. 多种时，我们增加映射次数来增加表达种类的关系，如食物链