题解 | #食物链#

并查集

开个三倍的fa数组，分别代表三种逻辑方向即可

#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5+5;
int fa[3*Nmax];
int n,k;
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void Merge(int x,int y){
    fa[find(x)] = find(y);
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>k;
    int cnt = 0,x,y,opt;
    for(int i = 1;i <= 3*n;i++)    //初始化并查集
        fa[i] = i;
    while(k--){
        cin>>opt>>x>>y;
        if(x > n || y > n) cnt++;
        else if(opt == 2){
            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);
            }
        }
        else{
            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);
            }
        }
    }
    cout<<cnt;
    return 0;
}