先上一波题目 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=200007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,m,ans=0; 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])%3; return fa[x]; } int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) fa[i]=i,d[i]=0; for(int i=1;i<=m;i++){ k=read(); x=read(); y=read(); if(x>n||y>n||(k==2&&x==y)){ans++; continue;} int p=find(x),q=find(y); //puts("qwq"); //printf("qwq%d %d\n",p,q); if(k==1){ if(p==q){if(d[x]!=d[y]) ans++;} else{ d[p]=(d[y]-d[x]+3)%3; fa[p]=q; } } else{ if(p==q){if(d[x]!=(d[y]+1)%3) ans++;} else{ d[p]=(d[y]-d[x]+4)%3; fa[p]=q; } } } printf("%d\n",ans); return 0; }