食物链题解
先简单说一下题目：
**n**个动物
两个操作：
**1 x y** 表示：x y是同类
**2 x y** 表示：x吃y
现在有k句话，假话以下条件，否则就是真话：
1. 与真话冲突是假话
2. x吃x是假话
3. x或者y 大于动物总编号n
思路：这不是普通的并查集，所以我们先回顾一个普通的并查集：包括“并”和“查”
(1)“并”的思想就是： 亲戚的亲戚就是也是亲戚，将他们划入一个集合中
(2)“查”的思想就是： 查看是否根节点相同，相同说明在一个集合内，否之不在
这道题目 ，不是简单地划入集合中，元素与元素之间存在关系，
（1）x和y是同类
（2）x吃y
（3）x被y吃
所以当我们划入集合地同时，重点要另外存他们之间的关系用dist[x]
这里重点解释一下什么是dist[x]含义：
dist[x]: x与x父节点之间的关系
(1) =0时： 表示同类关系
(2) =1时：表示x是吃x的父节点的关系
(3) =2时：表示x是被x的父节点吃的关系
对比普通并查集，代码实现上的不同：
**一，find()中**，找出父节点之后，还需要更新一下dist[x],因为我们最终是把两个结点划入一个集合中，和同一个根节点进行比较，意思就是说，我知道x和根节点的关系，也知道y和根节点的关系，自然就知道x和y之间的关系。所以我们更新dist使得x始终是和他的根节点进行比较
。
**二，在合并时候的不同**，在普通并查集中，我们对于两个点，知道他们是亲戚，即把他们之间的根节点统一，而带权并查集就是在连接的同时，将他们之间的关系也连起来，比如说这道食物链的题，给定了操作op==1是，他们之间的关系是同类，那么对他们的dist进行操作，op==2也是一样的道理，这个待会仔细讲一下，在代码注释里面
#include<bits/stdc++.h> using namespace std; const int N =5e4+6; int fa[N]; //存集合 int dist[N];//存关系 0时同类 1时吃 2时被吃 int find(int x) { int t = fa[x];//父节点 if(fa[x]!=x) { fa[x]=find(fa[x]);//fa[x]递归找根节点 dist[x]=(dist[x]+dist[t])%3;//主要是利用向量来理解，等式右边的dist[x]表示x->t, //dist[t]表示的是t->x的根节点，这样相加之后表示 //x->根节点，这里再重复一下，是为了之后判断， //因为比较使用根节点作为媒介的 } return fa[x]; } int main() { int n,k; cin>>n>>k; int ans=0; for(int i=1;i<=n;i++) { fa[i]=i; dist[i]=0;//初始化为0，x和x本身就是同类 } while(k--) { int op,x,y; cin>>op>>x>>y; if(x>n || y>n)//假话 1 { ans++; continue; } if(op==2 && x==y)//假话2 { ans++; continue; } //是否矛盾假话3 int fx= find(x); int fy= find(y); if(fx==fy)//如果在已经连接好了，就看他们之间的关系 { if(op==1)//如果是操作是同类的话，那他们不是同类关系就是假话 { if((dist[x]-dist[y]+3)%3!=0) //还是利用向量来理解 //这里就是上文说的好判断，利用同一个根节点 //dist[x]为x->根节点，dist[y]为y->根节点 //x->y就是dist[x]-dist[y],利用向量来理解 //提醒一下：+3是为了避免出现负数，mod3因为关系是循环 ans++; } if(op==2)//如果是吃的关系，那么如果不是吃就是假话 { if((dist[x]-dist[y]+3)%3!=1) ans++; } } //合并 ，如果他们之间还没有联系 else{ fa[fx]=fy;//将fy和fx合并 ，fx表示x的根节点，fy为y的 if(op==1)//是同类的关系。 //现在已知，x和fx的关系，y和fy，find里面求得的；也知道x和y的关系：同类（op==1给的） //那还要将fx和fy的关系联系起来，即用dist[fx]表示，不然就是散的 //关系式可为：fx->x , x->y, y->fy 那么dist[fx]=(-dist[x]+0+dist[y]+3)%3 { dist[fx] = (dist[y]-dist[x]+3)%3; } else{ //同理可得 dist[fx] = (dist[y]-dist[x]+1+3)%3; } } } cout<<ans;//最后输出结果 return 0; }