NOI2001 食物链-526互联

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int p[250010];
int fd(int x) {
    if (p[x] != x) p[x] = fd(p[x]);
    return p[x];
}
void un(int x, int y) {
    p[fd(x)] = fd(y);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= 250000; i++) p[i] = i;
    int ans = 0;
    while (m--) {
        int d, x, y;
        cin >> d >> x >> y;
        if (x > n or y > n) {
            ans++;
            continue;
        }
        if (d == 1) { // 说它们是同类
            if (fd(x + n) == fd(y) /* x吃y */ or fd(x) == fd(y + n) /* y吃x */) ans++;
            else {
                un(x, y);
                un(x + n, y + n);
                un(x + 2 * n, y + 2 * n);
            }
        } else { // 说x吃y
            if (fd(x) == fd(y + n) /* y吃x */ or fd(x) == fd(y) /* x和y是同类 */) ans++;
            else {
                un(x + n, y); // x的食物是y
                un(x + 2 * n, y + n); // x的天敌是y的食物
                un(x, y + 2 * n); // x是y的天敌
            }
        }
    }
    cout << ans << '\n';
}
/*
a的食物是a + n;
a的天敌是a + 2 * n
*/