一些真理
所以并查集到底是啥，是一个树？是一个连通分量？其实我们可以认为这是一个向量。为什呢？我们来看这个图。
假设存在关系A-B、B-C，根据这两个关系去构建并查集得到的结论不就是A-C有关系吗？实际上就是两个向量做加法，并查集的路径压缩就是在做这件事，向量路径缩短了，查询的速度自然而然就快起来了。而之前纠结的连通性问题其实就是向量存不存在的问题，换个角度来看，别有一番风味。结合一下实际，看一下一个经典案例。
http://poj.org/problem?id=1182
食物链问题，大意是某处存在三类生物，A能吃B，B能吃C，C能吃A，题目输入食物链的相关内容，要求检查输入食物链是否合理，这里单纯用一个数组描述两个节点rootX和X的关系已经不够，两个生物间存在同类，捕食和被捕食三种关系，这里用一个结构体来表示节点信息。
typedef struct Node { //并查集中节点的描述
int preNode; //当前节点的上一级
int relation; //节点和上一级节点的关系--0代表和上级是同类，1代表被上级吃，2代表吃上一级
} LineNode;
LineNode faction[50005]; //标记不同生物的关系
现在假设存在这样的关系，rootX吃X，rootY吃Y，不难看出这里二者构成了两个连通分量，如果此处指定rootX，rootY不相同，且X吃Y或者X和Y是同类，那么因为X和Y存在关系，那么这里要合并两个连通分量。
那么最后的结果应该是faction[AneY].preNode = AneX;但是只更新上下级是远远不够的，还应该更新关系域，关系域就涉及到向量的关系了，
在代码上写出来就是.
faction[AneY].relation = (faction[X].relation+(opt-1)-faction[Y].relation)%3;
//opt-1代表的是x->y的关系，对于方向反了的向量，这里取负数即可表示
更多内容可以参考这边文章，讲的很好，直接讲透了。
https://blog.csdn.net/niushuai666/article/details/6981689
下面是我的代码。
/**
* @file FoodLine.cpp
* @author mingke (1510181330@qq.com.com)
* @brief http://poj.org/problem?id=1182
* @version 0.1
* @date 2022-04-29
*
* @copyright Copyright (c) 2022
*
*/
#include<cstdio>
typedef struct Node { //并查集中节点的描述
int preNode; //当前节点的上一级
int relation; //节点和上一级节点的关系
} LineNode;
LineNode faction[50005]; //标记不同生物的关系
int findAncestor(int x);
using namespace std;
int main(void) {
int n, k;
scanf("%d %d", &n, &k);
int sum = 0; //假话的数量
int level = 1; //模拟的食物链层级
//初始化数据
for(int i = 1; i <= n; i++) {
//默认情况下，生物自成一派，和自己属于同类关系
faction[i].preNode = i;
faction[i].relation = 0;
}
while(k--) {
int opt, num1, num2;
scanf("%d %d %d", &opt, &num1, &num2);
if(num1 > n || num2 > n) {
sum++;
continue;
}
int AneX = findAncestor(num1); //第一个生物的祖先
int AneY = findAncestor(num2); //第二个生物的祖先
if(AneX != AneY) { //祖先不同，向量合并
faction[AneY].preNode = AneX;
faction[AneY].relation = (faction[num1].relation+(opt-1)-faction[num2].relation+3)%3; //加三防治减法弄出来负数
}else { //祖先相同
if(opt==1 && faction[num1].relation!=faction[num2].relation) { //只有当二者的关系域相等的时候才可能是同类
sum++; //假话
}
if(opt==2 && (faction[num2].relation-faction[num1].relation+3)%3!=1) { //向量模拟二者关系，比较是否成立
sum++; //假话
}
}
}
printf("%d\n", sum);
return 0;
}
//查找指定节点的双亲节点
int findAncestor(int x) {
//对于这里的路径压缩而言，要将节点X从其父节点挂载到其父节点的父节点，并更新关系域
if(faction[x].preNode == x) {
return x;
}
//准备更新节点
int pre = faction[x].preNode;
faction[x].preNode = findAncestor(pre); //更新父节点
faction[x].relation = (faction[pre].relation+faction[x].relation)%3; //更新关系
return faction[x].preNode;
}
// int faction[50005]; //标记不同生物的种类
// int fixLevel(int num);
// using namespace std;
// int main(void) {
// int n, k;
// scanf("%d %d", &n, &k);
// int sum = 0; //假话的数量
// int level = 1; //模拟的食物链层级
// //初始化数据
// for(int i = 1; i <= n; i++) {
// faction[i] = 0;
// }
// while(k--) {
// int opt, num1, num2;
// scanf("%d %d %d", &opt, &num1, &num2);
// if(num1 > n || num2 > n) {
// sum++;
// continue;
// }
// if(opt == 1) { //是同类
// if(faction[num1]==0 || faction[num2]==0) { //有一/两种生物第一次出现
// if(faction[num1]!=0) { //第一种生物出现过，以他为准
// faction[num2] = faction[num1];
// }else if(faction[num2]!=0) { //第二种生物出现过，以他为准
// faction[num1] = faction[num2];
// }else { //均未出现过，按照默认等级
// faction[num1] = faction[num2] = level%3;
// }
// }else {
// //两种生物均有自己的食物链层级，判断层级是否相同
// if(faction[num1] != faction[num2]) {
// sum++;
// }
// }
// }
// if(opt == 2) { //捕食关系
// if(num1 == num2) {
// sum++;
// continue;
// }
// if(faction[num1]==0 || faction[num2]==0) {
// if(faction[num1]!=0) { //如果捕食者的层级已知
// faction[num2] = fixLevel(faction[num1]-1);
// }else if(faction[num2]!=0) { //如果被捕食者的层级已知
// faction[num1] = fixLevel(faction[num2]+1);
// }else {
// //二者的层级均未确定
// faction[num2] = fixLevel(level%3);
// level++;
// faction[num1] = fixLevel(level%3);
// }
// }else {
// //二者食物链等级均存在，则比较二者的食物链等级
// if(faction[num1]-faction[num2]==1 || (faction[num1]==1 && faction[num2==3])) {
// // 正常的捕猎关系
// }else {
// sum++; //假话
// }
// }
// }
// }
// printf("%d\n", sum);
// return 0;
// }
// //确定生物食物链层级
// int fixLevel(int num) {
// if(num == 0) {
// return 3;
// }else if(num == 4) {
// return 1;
// }else {
// return num;
// }
// }
