题目链接：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 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", init(); while (K --) { int op, x, y; scanf("%d%d%d", 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\n", lie_num); return 0;}