种类并查集：维护循环关系。

/*
i+n表示i的天敌，i+2n表示i的捕食
*/
#include<bits/stdc++.h>
using namespace std ;
const int N = 50010 , M = 100010 ;
int f[N*3];
int find(int x){
    return x == f[x] ? f[x] : f[x] = find(f[x]);
}
void unite(int a , int b){
    a = find(a) , b = find(b);
    f[a] = b ;
}
int n , m ;

bool check(int a , int b){
    return find(a) == find(b);
}

int main(){
    cin >> n >> m ;
    for(int i = 1 ; i <= 3*n ; i++) f[i] = i ;
    int ans = 0 ; 
    while(m--){
        int t , a , b ;
        cin >> t >> a >> b ;
        if(a > n || b > n){
            ans++;
            continue;
        }
        if(t == 1){
            if(check(a , b+n) || check(a , b+2*n)){//如果b的天敌是a或者b的捕食是a，则a、b一定不是同类
                ans++;
            }else{
                unite(a , b);
                unite(a + n , b + n);
                unite(a + 2 * n , b + 2 * n);
            }
        }else{
            if(check(a , b) || check(a , b + 2*n)) ans++;//如果a与b是同类或者b的捕食是a，这a一定不能吃b
            else{
                unite(a , b + n);//b的天敌是a
                unite(a + n , b + 2*n);//a的天敌是b的捕食
                unite(a + 2*n , b);//a的捕食是b
            }
        }
    }
    cout << ans << endl;
}

作者：acwing_3931
链接：https://www.acwing.com/activity/content/code/content/460858/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。