P2024 [NOI2001] 食物链

*原题链接*

2024年当然要做P2024啦，看了眼题目，还是原来做过的题。这道题可以用种类并查集或带权并查集来做，而我只学会了种类并查集一种做法。分析题目中给出的关系，可以想到应该分3类集合，有同类集合，猎物集合，天敌集合，然后对于给出的每种关系判断是否冲突，再进行合并，就做完了。细节见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;int n,m,fa[N],ans;int find(int x){if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}int main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=3*n;i++) fa[i]=i;//x表示x的同类集合，x+n是x的猎物集合，x+n+n是x的天敌集合for(int i=1;i<=m;i++){int x,y,opt;cin>>opt>>x>>y;if(x>n||y>n){ans++;continue;}if(opt==1){if(find(x+n)==find(y)||find(x+n+n)==find(y)){ans++;continue;}fa[find(x)]=find(y),fa[find(x+n)]=find(y+n),fa[find(x+n+n)]=find(y+n+n);//x和y同类，每类集合中分别合并}else{if(find(x)==find(y)||find(x+n+n)==find(y)){ans++;continue;}fa[find(x)]=find(y+n+n),fa[find(x+n)]=find(y),fa[find(x+n+n)]=find(y+n);//x吃y，则y属于x的猎物集合，x属于y的天敌集合，x的天敌集合属于y的猎物集合}}cout<<ans<<endl;return 0;
}