题解 P2024 【食物链】

第一道提高加的题目 为此,写一个题解 ## 并查集的操作 有 合并与查找 而本题正好用到这些 ------------ 一的猎物的猎物 就是一的天敌 知道这一点 所以本题就是维护三个并查集 ```cpp #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; } ```