「带权并查集」食物链

食物链

原题链接：食物链

题目大意

给你N组数，每组数由三个数构成，如果第一个数是1，那么就说明后面两个数代表的物体是同类，如果第一个数是2，那么就代表第二个数吃第三个数，现在问你说假话的总数

题目题解

这个题作为带权并查集中的“拓展域”的模板题只能说过于经典，比上一道题简单，我们可以很简单的得到这道题的逻辑关系

我们需要将一个节点拆成三份，分别表示 同类域，捕食域，天敌域，那么就可以得到以下逻辑关系

• 若x, y是同类，那么他们的同类域、捕食域、天敌域相同，就合并
• 若x吃y，那么x的捕食域要加上y，y的天敌域要加上x，同理 x的同类域的捕食域也要加上y，y的同类域的天敌域也要加上x 又因为题目所说食物链是长度为3的环，那么 x的天敌域就是y的捕食域
• 若y吃x 与上面同理

如何判断是 x与y是同类 矛盾

• x的捕食域和y的同类域在同一集合，说明x 吃 y
• x的同类域和y的捕食域在同一集合，说明y 吃 x

如何判断是 x吃y 矛盾

• x的同类域和y的同类域在同一集合，说明x y是同类
• x的同类域和y的捕食域在同一集合，说明y 吃 x

通过以上信息，我们就能够得到代码如下

//#define fre yes

#include <cstdio>

int n, k;

const int N = 50005;
namespace Union {
    int par[N << 2];
    inline void init(int n) {
        for (int i = 1; i <= n; i++) {
            par[i] = i;
        }
    }

    int find(int x) {
        if(par[x] == x) return par[x];
        else return par[x] = find(par[x]);
    }

    inline void unite(int x, int y) {
        int a = find(x);
        int b = find(y);
        if(a == b) return ;

        par[a] = b;
    }

    inline bool same(int x, int y) {
        return find(x) == find(y);
    }
}

int main() {
    static int ans;
    scanf("%d %d", &n, &k);
    Union::init(n * 3);
    for (int i = 1; i <= k; i++) {
        int d, x, y;
        scanf("%d %d %d", &d, &x, &y);
        if(x > n || y > n) {
            ans++;
            continue;
        }
        if(d == 1) {
            if(Union::same(x, y + n) || Union::same(x, y + n * 2) || Union::same(x + n, y) || Union::same(x + n, y + 2 * n) || Union::same(x + 2 * n, y) || Union::same(x + 2 * n, y + n)) {
                ans++;
                continue;
            }

            Union::unite(x, y);
            Union::unite(x + n, y + n);
            Union::unite(x + 2 * n, y + 2 * n);
        }

        else if(d == 2) {
            if(Union::same(x, y) || Union::same(x, y + 2 * n) || Union::same(x + n, y) || Union::same(x + n, y + n) || Union::same(x + 2 * n, y + n) || Union::same(x + 2 * n, y + 2 * n)) {
                ans++;
                continue;
            }

            Union::unite(x, y + n);
            Union::unite(x + n, y + 2 * n);
            Union::unite(x + 2 * n, y);
        }
    } printf("%d\n", ans);
    return 0;
}