并查集+扩展域
扩展域并查集维护三个域：x_self同类，x_enemy天敌，x_eat捕食。
他们之间的关系：
假设有x，y两个动物，
如果题目给定x和y是同类，那么合并x_self,y_self和x_enemy,y_enemy和x_eat和y_eat。
前提条件是：x_self与y_eat不在同一个集合，x_eat与y_self不在同一个集合。
如果题目给定x吃y，这里我们注意到一点，由于题目给出的食物链关系是环形，因此我们可以由“x吃y”推断出“x的天敌是y的猎物”。
由此得到，合并x_eat,y_self和x_self,y_enemy和x_enemy,y_eat。
前提条件是：x_self和y_self不在一个集合，x_self和y_eat不在一个集合。
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 50006;
int fa[3*N];
int get(int x) {
if (x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
int main() {
int n, k, ans = 0;
cin >> n >> k;
for (int i = 1; i <= 3 * n; i++) fa[i] = i;
while (k--) {
int num, x, y;
scanf("%d %d %d", &num, &x, &y);
if (x > n || y > n || (num == 2 && x == y)) {
++ans;
continue;
}
if (num == 1 && (get(x) == get(y + n) || get(x + n) == get(y))) {
++ans;
continue;
}
if (num == 2 && (get(x) == get(y) || get(x) == get(y + n))) {
++ans;
continue;
}
if (num == 1) {
fa[get(x)] = get(y);
fa[get(x+n)] = get(y + n);
fa[get(x+2*n)] = get(y + 2 * n);
} else {
fa[get(x+n)] = get(y);
fa[get(x+2*n)] = get(y + n);
fa[get(x)] = get(y + 2 * n);
}
}
cout << ans << endl;
return 0;
}
原文：https://www.cnblogs.com/ruanmowen/p/12726837.html