题解 P2024 【食物链】

2018-04-20 13:30:23


第一道提高加的题目

为此,写一个题解

并查集的操作 有 合并与查找 而本题正好用到这些


一的猎物的猎物 就是一的天敌

知道这一点

所以本题就是维护三个并查集

#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define For(i,j,n) for(int i=(j);i<=(n);++i)
int fa[maxn];
int find(int x){
    if(fa[x]!=x)return fa[x]=find(fa[x]);
    else return x;
}
#define un_i_on(x,y) fa[find(x)]=find(y);
int main(){
    int n,m,ans=0;
    cin>>n>>m;
    //读入
    For(i,1,n*3)fa[i]=i;
    //初始化
    For(i,1,m){
        int a,b,c;
        cin>>a>>b>>c;
        if(b>n||c>n){++ans;continue;}
        //如果标号大于n,则定是假话
        if(a==1){
            if(find(b+n)==find(c)||find(b+2*n)==find(c)){++ans;continue;}
            //如果1是2的天敌或猎物,显然为谎言
            else{un_i_on(b,c);un_i_on(b+n,c+n);un_i_on(b+2*n,c+2*n);}
            //同类合并
        }
        else{
            if(b==c){++ans;continue;}
            if(find(b)==find(c)||find(b+2*n)==find(c)){ans++;continue;}
            else {un_i_on(b,c+2*n);un_i_on(b+n,c);un_i_on(b+2*n,c+n);}
        }
        //与上面类似
    }
    cout<<ans;
    return 0;
}