https://www.acwing.com/problem/content/242/

带权并查集，食物链

cpp
#include <stdio.h>
#include <stdlib.h>

#define MAXN 150000 // 3 * N 的最大值

int parent[MAXN];
int rank[MAXN];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

int isSameSet(int x, int y) {
    return find(x) == find(y);
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);

    // 初始化并查集
    for (int i = 0; i < 3 * N; ++i) {
        parent[i] = i;
        rank[i] = 0;
    }

    int falseCount = 0;

    for (int i = 0; i < K; ++i) {
        int D, X, Y;
        scanf("%d %d %d", &D, &X, &Y);

        if (X > N || Y > N) {
            falseCount++;
            continue;
        }

        if (D == 1) {
            // X and Y are the same type
            if (isSameSet(X, Y + N) || isSameSet(X, Y + 2 * N)) {
                falseCount++;
            } else {
                unionSet(X, Y);
                unionSet(X + N, Y + N);
                unionSet(X + 2 * N, Y + 2 * N);
            }
        } else if (D == 2) {
            // X eats Y
            if (isSameSet(X, Y) || isSameSet(X, Y + 2 * N)) {
                falseCount++;
            } else {
                unionSet(X, Y + N);
                unionSet(X + N, Y + 2 * N);
                unionSet(X + 2 * N, Y);
            }
        }
    }

    printf("%d\n", falseCount);

    return 0;
}