[HOJ] 78 食物鏈

并查集

#include<cstdio>
#define n 50001
int pa[n*3],N,K,x,y,cmd,ans;
int find(int k){
    if(pa[k]==k)return k;
    return pa[k]=find(pa[k]);
}
int un(int a,int b){
    pa[find(a)]=find(b);
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<n*3;i++)pa[i]=i;
    while(K--){
        scanf("%d%d%d",&cmd,&x,&y);
        if(x>N||y>N){
            ans++;
            continue;
        }
        if(cmd==1){
            if(find(pa[x])==find(pa[y+n])||find(pa[x])==find(pa[y+n*2]))
                ans++;
            else {
                un(x,y);
                un(x+n,y+n);
                un(x+n*2,y+n*2);
            }
        }
        else {
            if(find(pa[x])==find(pa[y+n*2])||find(pa[x])==find(pa[y]))
                ans++;
            else {
                un(x,y+n);
                un(x+n,y+n*2);
                un(x+n*2,y);
            }
        }
    }
    printf("%d\n",ans);
}