题目链接：https://www.luogu.com.cn/problem/P2024
解题思路：
我们用 (X+n) 来表示 吃 (X) 的集合，用 (X+2n) 来表示被 (X) 吃的集合，同时可以推导出 (X+2n) 是吃 (X+n) 的。
遇到“1 X Y”，则说明需要：
- 合并 (X) 和 (Y)；
- 合并 (X+n) 和 (Y+n)；
- 合并 (X+2n) 和 (Y+2n)。
但是在此之前需要先判断：
如果 (X) 和 (Y+n) 或者 (Y+2n) 属于同一个集合，则是假话。
遇到“2 X Y”，则说明需要：
- 合并 (X) 和 (Y+n)；
- 合并 (X+n) 和 (Y+2n)；
- 合并 (X+2n) 和 (Y)。
但是在此之前需要先判断：
如果 (X) 和 (Y) 或者 (Y+2n) 属于同一个集合，则是假话。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150050;
int n, K, f[maxn], lie_num;
void init() {
for (int i = 1; i <= 3*n; i ++) f[i] = i;
}
int func_find(int x) {
if (x == f[x]) return x;
return f[x] = func_find(f[x]);
}
void func_union(int x, int y) {
int a = func_find(x), b = func_find(y);
f[a] = f[b] = f[x] = f[y] = min(a, b);
}
int main() {
scanf("%d%d", &n, &K);
init();
while (K --) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (x > n || y > n) lie_num ++;
else {
if (op == 1) {
if (func_find(x) == func_find(y+n) || func_find(x) == func_find(y+2*n)) lie_num ++;
else func_union(x, y), func_union(x+n, y+n), func_union(x+2*n, y+2*n);
}
else { // op == 2
if (func_find(x) == func_find(y) || func_find(x) == func_find(y+2*n)) lie_num ++;
else func_union(x, y+n), func_union(x+n, y+2*n), func_union(x+2*n, y);
}
}
}
printf("%d
", lie_num);
return 0;
}