python/TangDou/AcWing/DisjointSet/240_KZY.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 150010;
int p[N];
int ans;
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void join(int x, int y) {
    int f1 = find(x), f2 = find(y);
    if (f1 != f2) p[f1] = f2;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= 3 * n; i++) p[i] = i; // 并查集初始化

    while (m--) {
        int x, y, t;
        cin >> t >> x >> y;
        // 说出大于n编号的动物，肯定是假话
        if (x > n || y > n) {
            ans++;
            continue;
        }
        if (t == 1) { // x和y同类
            if (find(x + n) == find(y) || find(x + 2 * n) == find(y)) {
                ans++;
                continue;
            }
            join(x, y);
            join(x + n, y + n);
            join(x + 2 * n, y + 2 * n);
        }
        if (t == 2) { // x吃y
                      // +n  天敌，+2n 食物
            if (find(x) == find(y) || find(x + n) == find(y)) {
                ans++;
                continue;
            }
            join(x, y + n);
            join(x + n, y + 2 * n);
            join(x + 2 * n, y);
        }
    }
    printf("%d\n", ans);
    return 0;
}