题面：
有三类动物 \(A,B,C\)，\(A\) 吃 \(B\) ，\(B\) 吃 \(C\) ，\(C\) 吃 \(A\) 。
现有 \(N\) 个动物，以 \(1∼N\) 编号，每个动物都是 \(A,B,C\) 中的一种。
用两种说法对这 \(N\) 个动物所构成的食物链关系进行描述：
第一种说法是1 X Y，表示 \(X\) 和 \(Y\) 是同类。
第二种说法是2 X Y，表示 \(X\) 吃 \(Y\) 。
一共 \(K\) 句话，当一句话满足下列三条之一时，这句话就是假话，否则就是真话：
1、当前的话与前面的某些真的话冲突，就是假话；
2、当前的话中 \(X\) 或 Y 比 \(N\) 大，就是假话；
3、当前的话表示 \(X\) 吃 \(X\) ，就是假话。
输出假话总数。
原题链接：240. 食物链 - AcWing
并查集：维护额外信息
扩展域
建立一个初始域和两个扩展域，分别为同类域 p[x] 、捕食域 p[x+n] 和被捕食域 p[x+n+n]。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, k, x, y;
int cnt, op;
int p[3 * N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> k;
//建立扩展域时，注意三个域都需要赋初值
for (int i = 1; i <= 3 * n; i++) p[i] = i;
while (k--) {
cin >> op >> x >> y;
// x或y比n大，或x吃x，即为假话
if (x > n || y > n || (x == y && op == 2)) {
cnt++;
continue;
}
if (op == 1) {
//如果x捕食y，或者y捕食x，即为假话
if (find(x + n) == find(y) || find(y + n) == find(x)) cnt++;
else {
p[find(x)] = find(y);
p[find(x + n)] = find(y + n);
p[find(x + n + n)] = find(y + n + n);
}
}
else {
//x与y为同类，或者y捕食x（x在y的捕食域中），即为假话
if (find(x) == find(y) || find(x) == find(y + n)) cnt++;
else {
p[find(x + n)] = find(y);
p[find(x + n + n)] = find(y + n);
p[find(x)] = find(y + n + n);
}
}
}
cout << cnt;
}
带边权
p[]数组：储存当前点所在集合的根节点；d[]数组：储存该点到其根节点的距离。
\(d\) 数组更新的原则：该节点到根节点的距离 = 该点到父节点的距离 + 父节点到根节点的距离find()函数的作用：- 寻找根节点，确定节点所在集合；
- 更新当前节点到根节点的距离。
同余定理的应用：同一集合内必然同余
- 同余定理：给定一个正整数 \(m\)，如果两个整数 \(a\) 和 \(b\) 满足 \((a-b)\) 能够被 \(m\) 整除，即 \((a-b)/m\) 得到一个整数，那么就称整数 \(a\) 和 \(b\) 对模 \(m\) 同余。
- 对于当前节点到根节点的距离 \(d\bmod 3\) 可得，\(0\)：同类；\(1\)、\(-2\)：捕食；\(2\)、\(-1\)：被捕食。
因为三种关系为线性轮回，所以已知 \(a\) 捕食 \(b\) ，\(b\) 捕食 \(c\) ，就可以得出 \(c\) 能捕食 \(a\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, x, y;
int cnt, op;
int p[N]; //根节点
int d[N]; //到根节点的距离
int find(int x) {
if (p[x] != x) {
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) p[i] = i;
while (k--) {
cin >> op >> x >> y;
// x或y比n大，或x吃x，即为假话
if (x > n || y > n || (x == y && op == 2)) {
cnt++;
continue;
}
int px = find(x);
int py = find(y);
int t = d[x] - d[y];
if (op == 1) {
//同类却不同余，即为假话
if (px == py && t % 3) cnt++;
else if (px != py) {
p[px] = py;
d[px] = d[y] - d[x];
}
}
else {
if (px == py && (t - 1) % 3) cnt++;
else if (px != py) {
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
cout << cnt;
}