AcWing 240. 食物链

我们定义：对于任意一个 \(i\)：

• \(i\) 表示其本身。
• \(n + i\) 表示 \(i\) 的天敌。
• \(2n + i\) 表示 \(i\) 的猎物。

（您可能不知道定义是最难想的）

题目中对于假话的定义是：

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X 或 Y 比 N 大，就是假话；
3. 当前的话表示 X 吃 X，就是假话。

其中，第 \(2\)、\(3\) 条容易判断（直接特判），那第 \(1\) 条呢？

首先声明一下，只有真话才会被录入信息。

• 如果 \(x\) 和 \(y\) 是同类，若 \(x\) 是 \(y\) 的天敌或猎物，那么是假话。
• 如果 \(x\) 吃 \(y\)，若 \(x\) 和 \(y\) 是同类，那么是假话。
• 如果 \(x\) 吃 \(y\)，若 \(x\) 是 \(y\) 的猎物，那么是假话。
• 如果 \(x\) 吃 \(y\)，若 \(y\) 是 \(x\) 的天敌，那么是假话。

关于 \(i\) 的天敌和猎物，我们已经有所定义。

所以，到这里，应该很容易看出来是并查集。

看出来是并查集，就很容易做了。

若您不会并查集，请移步至 AcWing 836. 合并集合。

最后注意：合并时也有些讲究。（自己想想啊呀，待会看代码）

Code：

#include <iostream>
#include <cstdio>
using namespace std;
int n, k, ans = 0;
int fa[150010]; //注意数组开 3 倍。
int find (int x) {
    if(fa[x] != x) return fa[x] = find(fa[x]);
    return fa[x];
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= 3 * n; i ++ )
        fa[i] = i; //基本初始化。
    while (k -- ) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(x > n || y > n) { ans ++; continue; }
        if(op == 1) {
            if(find(x) == find(y + n)) {
                ans ++;
                continue;
            }
            if(find(x) == find(y + 2 * n)) {
                ans ++;
                continue;
            }
            fa[find(y)] = find(x);
            fa[find(y + n)] = find(x + n);
            fa[find(y + 2 * n)] = find(x + 2 * n);
        }
        if(op == 2) {
            if(x == y) { ans ++; continue; }
            if(find(x) == find(y)) { ans ++; continue; }
            if(find(x) == find(y + 2 * n)) {
                ans ++;
                continue;
            }
            fa[find(x)] = find(y + n);
            fa[find(y)] = find(x + 2 * n);
            fa[find(x + n)] = find(y + 2 * n);
        }
        
    }
    printf("%d", ans);
    return 0;
}

若您觉得有帮助，就点个赞吧。

更多精彩请关注我的博客号~

祝各位 rp++ ！