本题目是一道非常好的并查集练习题，有两种并查集的解法，分别是扩展域并查集、带权并查集，下面分别进行介绍：
一、扩展域并查集
1、三点认知
-
两个同类元素的天敌集合是同一个集合，猎物集合也是同一个集合。
-
天敌的天敌是猎物 (因为是食物环嘛)
-
猎物的猎物是天敌 (因为是食物环嘛)
2、扩展域思想
(1sim n)个元素扩大为(1sim 3n)个元素，使用([1，3n])个并查集（每一个并查集中的所有元素都具有同一种特性，不同并查集中不存在相同元素）来维护(3n)元素彼此的关系。
在这里(x)元素，(x+n)元素，(x+2n)元素三者的关系被定义为：
(x)元素所在集合中所有(∈[1，n])的元素都是(x)元素的同类
(x+n)元素所在集合中所有(∈[1，n])的元素都是(x)元素的天敌
(x+2n)元素所在集合中所有(∈[1，n])的元素都是(x)元素的猎物
(x+n)元素所在的集合中所有(∈[1，n])的元素都是(x+2n)元素的猎物
当得到一句关于两个元素(x，y)彼此关系的描述时，如果已知目前(x,y)它们各自的猎物和天敌，以及它们是否是同类，就可以判断这句描述的真假。
可以通过(x+n)元素来确定(x)元素目前已知的天敌，也可以通过(x+2n)元素来确定(x)元素目前的猎物，还可以通过(x)元素本身来确定(x)的同类。
于是就能够进行语言真假的判断了!
对于一句真话:
当(x)元素,(y)元素是同类时，将他们两者的天敌集合（(x+n)元素与(y+n)元素所在集合）和猎物集合（(x+2n)元素与(y+2n)元素所在集合）以及自身所在的集合分别合并。
当(x)元素是(y)元素的天敌时，将(x)元素所在集合与(y)元素的天敌集合合并，将(y)元素所在集合和(x)元素的猎物集合合并，将(x)元素的天敌集合和(y)元素的猎物集合合并
3、实现代码
#include<bits/stdc++.h>
using namespace std;
const int N = 150010;
int fa[N];
int ans;
//带扩展域的并查集
/**
* 功能：寻找祖先
* @param x
* @return
*/
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
//加入家族集合中
void join(int x, int y) {
int f1 = find(x), f2 = find(y);
if (f1 != f2)fa[f1] = f2;
}
int main() {
int n, m;
cin >> n >> m;
//开三个并查集，合用一个数组表示
//对于每种生物：设x为本身，x+n为猎物，x+2*n为天敌
for (int i = 1; i <= 3 * n; i++) fa[i] = i; //初始化
while (m--) {
int x, y, t;
cin >> t >> x >> y;
// 太大了，越界了，肯定是假话
if (x > n || y > n) {
ans++;
continue;
}
//xy同类
if (t == 1) {
//如果y是x的天敌或猎物，为谎言
if (find(x + n) == find(y) || find(x + 2 * n) == find(y)) {
ans++;
continue;
}
//x的同类和y的同类，x的猎物是y的猎物，x的天敌是y的天敌
join(x, y);
join(x + n, y + n);
join(x + 2 * n, y + 2 * n);
}
//y是x的猎物
if (t == 2) {
//如果x是y的同类或猎物，为谎言
if (find(x) == find(y) || find(x + 2 * n) == find(y)) {
ans++;
continue;
}
join(x, y + 2 * n);//x的同类是y的天敌
join(x + n, y);//x的猎物是y的同类
join(x + 2 * n, y + n); //x的天敌是y的猎物
}
}
printf("%d
", ans);
return 0;
}
二、带权并查集
功能：查询祖先+修改父节点为祖先+更新节点到根的距离（通过到父节点的距离累加和）
(d[i])的含义：第 (i) 个节点到其父节点距离。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
const int M = 3;
/**
带权并查集：
(1)不管是同类，还是吃与被吃的关系，都把它们放到同一个集合中去,关系用距离描述:
0:同类，1：猎物, 2:天敌
(2)通过上面的记录关系，就可以推理出任何两个节点的关系。
*/
int n, m;
int p[N]; //父亲是谁
int d[N]; //i结点到父结点的距离
int res; //假话的个数
/**
* p是指节点i的父节点是谁
* d是指节点i到自己父亲的距离
* d[x]=1 : x吃根结点
* d[x]=2 : x被根结点吃
* d[x]=0 : x与根结点是同类
* @param x
* @return
*/
int find(int x) {
if (p[x] != x) {
//这里将最祼并查集的代码拆开了
int t = find(p[x]);
//中间加了一个维护距离的代码,之所以这样做，是因为这里需要使用p[x]更新压缩路径后d[x]的值，不用破坏
d[x] = (d[p[x]] + d[x]) % M;
//修改p[x]
p[x] = t;
}
return p[x];
}
int main() {
//优化输入
ios::sync_with_stdio(false);
cin >> n >> m;
//并查集初始化
for (int i = 1; i <= n; i++) p[i] = i;
//m个条件
while (m--) {
int t, x, y;
cin >> t >> x >> y;
//如果出现x,y的序号，大于最大号，那么肯定是有问题，是假话
if (x > n || y > n) {
res++;
continue;
}
//找出祖先
int px = find(x), py = find(y);
//t==1,同类
if (t == 1) {
//合并并查集
if (px != py) {
p[px] = py;
d[px] = (d[y] - d[x] + M) % M;
} else if ((d[x] - d[y] + M) % M) res++;//不是同类,结果值++
} else {
//t==2,表示X吃Y
//不在同一个家族内，描述刚录入进来的信息，肯定是真话，记录这个信息
if (px != py) {
p[px] = py;
d[px] = (d[y] + 1 - d[x] + M) % M;
} else if ((d[y] + 1 - d[x] + M) % M) res++; //同一个家族,但距离并不是1,那就是错误答案
}
}
//输出大吉
printf("%d
", res);
return 0;
}
代码解释：
