题目在这里
题意
动物王国中有三类动物 \(A,B,C\)，这三类动物的食物链构成了有趣的环形。\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。
现有 \(N\) 个动物，以 \(1 \sim N\) 编号。每个动物都是 \(A,B,C\) 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 \(N\) 个动物所构成的食物链关系进行描述：
- 第一种说法是 \(1\) \(X\) \(Y\)，表示 \(X\) 和 \(Y\) 是同类。
- 第二种说法是 \(2\) \(X\) \(Y\)，表示 \(X\) 吃 \(Y\)。
此人对 \(N\) 个动物，用上述两种说法，一句接一句地说出 \(K\) 句话，这 \(K\) 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 \(X\) 或 \(Y\) 比 \(N\) 大，就是假话；
- 当前的话表示 \(X\) 吃 \(X\)，就是假话。
你的任务是根据给定的 \(N\) 和 \(K\) 句话，输出假话的总数。
分析
用拓展域并查集, \([i,n]\)表示同类, \([i+n, 2 * n]\) 表示猎物, \([i + 2 * n, i + 3 * n]\) 表示天敌
猎物的猎物是天敌，天敌的天敌是猎物
- 对于查询\(1\)如果 \(X\) \(Y\) 互吃则为假
- 对于查询\(2\)如果 \(X\) \(Y\) 是同类或 \(Y\) 吃 \(X\) 则为假
代码
点击查看代码
#include <bits/stdc++.h>using namespace std;
const int MAXN = 200010;
int n, k, fa[MAXN], ans = 0;
// i~n 同类, i + n ~ 2 * n 猎物, i + 2 * n ~ i + 3 * n 天敌
int find(int x)
{if(fa[x] == x) return x;return fa[x] = find(fa[x]);
}int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n >> k;for(int i = 1; i <= 3 * n; i++) fa[i] = i;for(int i = 0; i < k; i++){int op, x, y;cin >> op >> x >> y;if(x > n || y > n) ans++;else if(op == 1){// 如果x, y不互吃 if(find(x) != find(y + n) && find(x) != find(y + 2 * n) && find(x + n) != find(y) && find(x + 2 * n) != find(y)) {fa[find(y)] = find(x); // x 与 y 合并 fa[find(y + n)] = find(x + n); // x的猎物与y的猎物合并 fa[find(y + 2 * n)] = find(x + 2 * n); // y的天敌与x的天敌合并 }else ans++;}else if(op == 2){// 如果 y 吃 x if(find(x) == find(y) || find(x) == find(y + n) ||find(x + 2 * n) == find(y)) ans++;else {fa[find(y + 2 * n)] = find(x); // y 的天敌与 x合并 fa[find(x + n)] = find(y); // x 的猎物与 y合并 fa[find(x + 2 * n)] = find(y + n); // x的天敌与 y的猎物合并 }}}printf("%d", ans);return 0;
}