题目：P2024 [NOI2001] 食物链 - 洛谷
思路：
- 假设一条链状结构均是吃与被吃的关系 x <- p1<- p2<- p3等
由于C->B->A->C，在链上，与x距离0为同类，1为x吃其，2为x被其吃
- 用并查集来存储所有节点，无论节点与其父亲节点是何种关系
- 用一个权值
d[x]表示 x 到父亲节点的距离(关系)：0(同类)、1(x吃其父亲节点)、2(x被其父亲节点吃)
在路径压缩的过程中一步一部累加x到根节点的距离，最后x连接到根，d[x]即可表示与其根的关系
- x与y同一根时，
(d[x]-d[y]+3)%3表示 x 与 y 的关系：0(同类)、1(x吃y)、2(x被y吃)
- x与y不同根，则需要合并，将x的根的父亲设置为y的根
同类合并：(d[x]+d[fx] -d[y]+3)%3==0 ，即d[fx]=(d[y]-d[x]+3)%3
x吃y:(d[x]+d[fx] -d[y]+3)%3==1 ，即d[fx]=(d[y]-d[x]+1+3)%3
代码：
#include<iostream>
using namespace std;const int N=50010;
int p[N],d[N];
//d[i]可取 0 1 2，分别代表与其父节点的关系是 同类，吃其父节点，被其父节点吃
int find(int x)
{if(p[x]!=x){//如果x的父亲不是根，则进入,进行路径压缩，同时将d[x]更新为与根的关系int u=find(p[x]);//求p[x]的根并记录，实现路径压缩后d[p[x]]即为p[x]与根的关系d[x]=(d[x]+d[p[x]])%3;//x与根的关系=(x与父节点的关系+父节点与根的关系)%3p[x]=u;}return p[x];
}int main()
{int n,k,res=0;scanf("%d%d",&n,&k);for(int i=0;i<=n;i++)p[i]=i;while(k--){int op,x,y;scanf("%d%d%d",&op,&x,&y);int fx=find(x),fy=find(y);if(x>n||y>n)res++;else if(op==1){if(fx==fy&&(d[x]-d[y]+3)%3!=0)res++;//根相同，且非同类，违背真话else{p[fx]=fy;d[fx]=(d[y]-d[x]+3)%3;}}else{if(x==y||(fx==fy&&((d[x]-d[y]+3)%3==0||(d[x]-d[y]+3)%3==2)))res++;//1.x等于y，2.根相同，且关系已经明了不是x吃y，违背真话else{p[fx]=fy;d[fx]=(d[y]-d[x]+1+3)%3;}}}cout<<res;return 0;
}
