先上一波题目 https://www.luogu.org/problem/P2024
通过这道题复习了一波并查集，学习了一波带权值操作
首先我们观察到 所有的环都是以A->B->C->A这样的三元环形式存在的
不同动物之间的关系有三种 同类 吃 被吃
那么我们用+1表示吃 +2表示被吃 0表示同类就可以很清楚的记录不同动物的关系了
这样我们只需要在合并并查集的时候对路径的权值进行一定的操作 就可以记录不同动物之间的关系以便查询了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,ans=;
int k,x,y;
int fa[M],d[M];
int find(int x){
int f=fa[x];
if(f==x) return x;
fa[x]=find(f);
d[x]=(d[f]+d[x])%;
return fa[x];
}
int main(){
n=read(); m=read();
for(int i=;i<=n;i++) fa[i]=i,d[i]=;
for(int i=;i<=m;i++){
k=read(); x=read(); y=read();
if(x>n||y>n||(k==&&x==y)){ans++; continue;}
int p=find(x),q=find(y);
//puts("qwq");
//printf("qwq%d %d\n",p,q);
if(k==){
if(p==q){if(d[x]!=d[y]) ans++;}
else{
d[p]=(d[y]-d[x]+)%;
fa[p]=q;
}
}
else{
if(p==q){if(d[x]!=(d[y]+)%) ans++;}
else{
d[p]=(d[y]-d[x]+)%;
fa[p]=q;
}
}
}
printf("%d\n",ans);
return ;
}