食物链可以说是一道非常经典的种类并查集问题，我们定义偏移量的概念，类似于向量，当fx-->x=1表示fx吃x，fx-->x=2表示x吃fx，fx-->x=0表示x于fx是同类，用一个数组flag[i]记录，表示i的祖先到i的偏移量，则题目中需要我们维护或判断x-->y的偏移量是否是opt-1，定义x的祖先为fx，y的祖先为fy，则如果合并fx与fy，fx-->x-->y-->fy，即flag[fy]=flag[x]+opt-1+(-flag[y])，这样就能合并fx与fy，如果fx=fy，则我们需要知道题目所给出的x-->y的关系是否合法，x-->y的偏移量即为flag[y]-flag[x]，再判断是否等于opt-1即可，至于flag数组在路径压缩中的维护，自己推一推就好了，这里就不再赘述。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 50005 int father[maxn],n,k,tot; int flag[maxn]; int getfather(int x) { int temp=father[x]; if (x!=father[x]) father[x]=getfather(father[x]); flag[x]=(flag[temp]+flag[x])%3; return father[x]; } int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) father[i]=i; for (int i=1;i<=k;i++) { int opt,x,y; scanf("%d%d%d",&opt,&x,&y); if (x>n||y>n) {tot++;continue;} if (x==y&&opt==2) {tot++;continue;} int fx=getfather(x); int fy=getfather(y); if (fx!=fy) { flag[fy]=(flag[x]+opt-1-flag[y]+3)%3; father[fy]=fx; } else if ((flag[y]-flag[x]+3)%3!=opt-1) tot++; } printf("%d\n",tot); return 0; }