题解 | #食物链#

#include <iostream>

using namespace std;

int fa[2000010];

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int a, int b)
{
    fa[find(a)] = find(b);
}

int main()
{
    int n, k;
    cin >> n >> k;

    for(int i = 1; i <= 3 * n; i++) fa[i] = i;

    int cnt = 0;
    while(k --)
    {
        int op, x, y;
        cin >> op >> x >> y;

        if(x > n || y > n) {cnt ++; continue;}

        if(op == 1)
        {
            if(find(x) == find(y + n) || find(x) == find(y + 2 * n)) cnt ++;
            else merge(x, y), merge(x + n, y + n), merge(x + 2 * n, y + 2 * n);
        }
        else
        {
            if(find(x) == find(y) || find(x) == find(y + 2 * n)) cnt ++;
            else merge(x, y + n), merge(x + n, y + 2 * n), merge(x + 2 * n, y);
        }
    }

    cout << cnt;

    return 0;
}