剖析例题食物链
初步分析
例题中给了我们很多零散的条件，最后要让我得到一个结果。对于这种须高效地维护关系，并快速判断是否产生了矛盾，并查集就可以很好的发挥作用。对于本题，需要维护的信息有两个：
⭐是否是同类
⭐是否存在捕食关系
解决思路
对于每只动物i创建3个元素i-A、i-B、i-C,并用这总共的3*N个元素建立并查集。这个并查集维护如下信息：
■ i-X 表示 i是属于X这个物种(或者说是集合)
■ 并查集里的每一个组表示组内所有元素代表的情况都同时发生或不发生。
例如，如果i-A和j-B在同一个组里，就表示如果i属于物种A那么,j一定属于物种B。因此，对于每一条信息，只需要按照下面进行操作就可以了：
🔗 第一种，x 和 y 属于一个集合，那么合并 x-A 和 y-A, x-B 和 y-B,x-C 和 y-C。
🔗 第二种，x 吃 y,那么合并 x-A 和 y-A, x-B 和 y-B,x-C 和 y-C。
■ 需要注意的是，合并之前要先判断合并操作是否会触发矛盾，比如对于第一种而言，就要先保证x-A 和 y-B 或者 y-C在同一组里。
存在的疑问
可能有小伙伴想问，为什么无论在不在一个集合里，都要执行合并的操作了？这是为了符合路径压缩的思想，在更多的结点最后都是和根结点直接产生关系，可以实现在数据量庞大的时候，依旧可以快速的执行合并操作。
举个栗子
在军营里，一个说我比旅长小两级，另一个说，我比军长大一级，另一个又说，我不太行，我只比排长大一点。想想通过这种散乱的描述，要获得有用信息会很困难。
假如换个维护信息的方式，一个说，我比将军小四级，另一个说，我比将军小两级，另一又说，我比将军小七级，最后一个，我就是将军…
那么，很明显的可以体会出来，后一种直接把老大作为维护的根本，那么获得的信息会更有秩序，也会更快。
对于并查集而言，并查集的找到树的根和路径压缩主要就是落实上述的事情，通过不断的和老大建立直接联系，使得查询和修改变得更加容易和轻松。
代码逐步落实
初始化并查集
因为本思路通过维护的是三个不同才层次的集合来实现对题中三个物种的区分
元素x代表的是x-A
元素x + N 代表的是x -B
元素x + 2* N 代表的是 x-C
这里对于N可以理解为权重。
处于不带权重的数组中的x就是最基础的物种A
处于带了一层权重N的数组范围的则是物种B
处于带了两层权重的数组范围的则是物种C
/***********全局变量的声明**********/ const int MAX_N = 150030,MAX_K = 100010; const int MAX_N = 150030,MAX_K = 100010; int N,K; int par[MAX_N];//维护父亲结点的信息 int height[MAX_N];//树的高度 /**********主函数*************/ init(N * 3);
K次循环，录入数据,处理数据
判断假话
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 X 吃 X，就是假话。
第一个if解决的是有没有符合范围，不符合范围？假话！❌
现在进入if的都是符合范围的数据
处理情况1：判断是同类
if(same(x,y + N) || same(x,y+2*N)) ans ++;
如果给出的操作是说x 和 y 是同类，但是通过same函数计算出，x所在的物种A和y所在的物种B(y+N 是在物种B所在的数组范围)的祖先相同，或者x所在的物种A和y所在的物种C的祖先一样。这合理吗？这不合理，假话~，对于是同一个物种的，就将它们维护起来，方便以后查询
处理情况2：判断捕食的情况
如果给出的操作是说x捕食y,但是我传入的数据中，x和y是同类
///
same(x,y)
或者x是吃y的，结果算出来祖先一样的
same(x,y+2*N)
这合理吗？这不合理，假话
for(int i = 0; i < K;i++) { int t,x,y; scanf("%d %d %d",&t,&x,&y); //当前的话中 X 或 Y 比 N 大，就是假话； if(x <0 || x > N || y < 0 || y > N) { ans ++; continue; } } if(t == 1)//处理x 和 y 是同类的情况 { if(same(x,y + N) || same(x,y+2*N)) ans ++; else { unite(x,y); unite(x+N,y+N); unite(x+N*2,y+N*2); } }else //处理 "x吃y的情况" { if(same(x,y) || same(x,y+2*N)) ans ++; else { unite(x,y+N); unite(x+N,y+2 * N); unite(x + 2*N , y); } }
输出结果，完美解决
printf("%d\n",ans);
参考代码二(C++版本)
仙术直通车
#include <iostream> using namespace std; const int N = 50010; int n,m; //p数组是并查集的父结点，d数组是距离 int p[N],d[N]; //并查集的核心函数 int find(int x) { //如果x不是根节点 if(p[x] != x) { //提前存放上x的父结点通过find函数递归找到的祖宗结点的信息 int t = find(p[x]); //因为d[x]存放的就是x到它原本的父节点的距离，现在再加等于x的父节点p[x]到根节点的距离，就是x到根节点的距离 d[x] += d[p[x]]; p[x] = t;//更新x父结点的信息，让x的祖宗结点直接当x的父结点 } return p[x]; } int main() { scanf("%d%d",&n,&m); //初始化每一个点 for(int i = 1;i <= n;i++) p[i]= i; int res = 0;//假话的数量 //k次询问 while(m--) { int t,x,y; scanf("%d%d%d",&t,&x,&y); if(x > n || y > n) res ++; else { //找出x 的根节点 px 和 y的根节点py int px = find(x) , py = find(y); if(t == 1) //x 和 y是同类的情况 { //如果两个是在一颗树上的，但是模出来结果不一样，那就不是同类 if(px == py && (d[x] - d[y]) % 3) res ++; else if (px != py) { p[px] = py; d[px] = d[y] - d[x]; } } else // x 吃 y的情况 { //如果在同一颗树上 d[x] 比 d[y]大的时候。x可以吃y if(px == py && (d[x] - d[y] - 1) % 3) res ++; else if(px != py)//不在一棵树上，现在把x合并到y这颗树上 { p[px] = py; d[px] = d[y] + 1- d[x]; } } } } printf("%d\n",res); return 0; }
