空降锣鼓

空降OJ

题解：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int d,x,y;
int ans;
int fa[500050];
int find(int x){//找爸爸
    if(fa[x]==x)    return fa[x];
    return find(fa[x]);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n*3;i++)//开三个并查集风别表示自己的
        fa[i]=i;//天敌，同类和猎物
    for(int i=1;i<=k;i++){
        cin>>d>>x>>y;
        if(x>n || y>n){//最初判断是否大于n
            ans++;
            continue;
        }
        int t1=find(x);//三个并查集
        int t2=find(y);
        int t3=find(x+n);
        int t4=find(y+n);
        int t5=find(x+n+n);
        int t6=find(y+n+n);
        if(d==1){
            if(t1==t4 || t2==t3)//互为实物
                ans++;
            else{//合并家族
                fa[t1]=t2;
                fa[t3]=t4;
                fa[t5]=t6;
            }
        }
        if(d==2){
            if(t1==t2 || t1==t4)//ab是同类或者b吃a
                ans++;
            else{//合并家族
                fa[t3]=t2;
                fa[t5]=t4;
                fa[t1]=t6;
            }
        }
    }
    cout<<ans;
    return 0;
}