洛谷 P2024：[NOI2001] 食物链 ← 扩展域并查集
【题目来源】
https://www.luogu.com.cn/problem/P2024
【题目描述】
动物王国中有三类动物 A，B，C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1∼N 编号。每个动物都是 A，B，C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 X 和 Y 是同类。
第二种说法是 2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
（1）当前的话与前面的某些真的话冲突，就是假话；
（2）当前的话中 X 或 Y 比 N 大，就是假话；
（3）当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
【输入格式】
第一行两个整数，N，K，表示有 N 个动物，K 句话。
第二行开始每行一句话。格式见题目描述与样例。
【输出格式】
一行，一个整数，表示假话的总数。
【输入样例】
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
【输出样例】
3
【数据范围】
对于全部数据，1≤N≤5×10^4，1≤K≤10^5。
∣X∣,∣Y∣<2^32。
【算法分析】
● 基础并查集：https://blog.csdn.net/hnjzsyjyj/article/details/146948171
int find(int x) { if(x!=pre[x]) pre[x]=find(pre[x]); return pre[x]; } void merge(int x,int y) { int a=find(x); int b=find(y); if(a!=b) pre[a]=b; } for(int i=1; i<=n; i++) pre[i]=i;● 扩展域并查集：https://blog.csdn.net/hnjzsyjyj/article/details/162165317扩展域并查集
（1）扩展域并查集是一种高效处理多关系问题的数据结构，通过扩展元素的“逻辑域”来维护复杂关系，适用于传统基础并查集无法解决的场景。缺点是需扩展多倍数组，空间占用较高。
（2）在扩展域并查集中，父数组的大小为 n×k，其中 n 是元素总数，k 是每个元素的“逻辑域”数。
（3）扩展域并查集中的“逻辑域”数等于给定问题中"互斥关系的种类数”。
例如，在食物链问题中，物种间的关系不是简单的“吃”与“被吃”，而是循环依赖（如 X 吃 Y、Y 吃 Z、Z 吃 X），是一个封闭的循环。在这个循环中，每个物种有三种可能的“角色”（同类域、食物域、天敌域），且这三种角色循环轮替。
（4）为什么必须用“域”来表示？
并查集仅能判断两个元素是否属于同一连通集合，只能描述无向等价关系，无法表达单向约束。
食物链里 “X 吃 Y” 是单向关系，直接用原始动物节点无法区分 “X 吃 Y” 和 “Y 吃 X”。
因此需要将同一个动物拆出三类逻辑分身：同类域、食物域、天敌域，代表该动物在不同捕食关系中的身份；通过合并不同动物对应域的分身，把单向捕食约束转化为无向集合连通关系，用集合归属间接存储整套有向逻辑。
（5）由于食物链的底层逻辑是循环依赖（如 X 吃 Y、Y 吃 Z、Z 吃 X），故针对动物 i，用i表示 i 的同类域 、用i+n表示 i 的食物域、用i+2n表示 i 的天敌域。
当声明“X 吃 Y”时，本质上是在说：X 的食物域 = Y 的同类域、X 的天敌域 = Y 的食物域、X 的同类域 = Y 的天敌域。
当声明“X 吃 Y”时，其关系代码如下所示。
merge(x, y+2*n); // X 的同类域 = Y 的天敌域 merge(x+n, y); // X 的食物域 = Y 的同类域 merge(x+2*n, y+n); // X 的天敌域 = Y 的食物域【算法代码】
#include <bits/stdc++.h> using namespace std; const int N=5e4+5; int pre[N*3]; int find(int x) { if(x!=pre[x]) pre[x]=find(pre[x]); return pre[x]; } void merge(int x,int y) { int a=find(x); int b=find(y); if(a!=b) pre[a]=b; } int main() { int n,k,ans=0; cin>>n>>k; for(int i=1; i<=3*n; i++) pre[i]=i; while(k--) { int op,x,y; cin>>op>>x>>y; if(x>n || y>n) { ans++; continue; } if(op==1) { if(find(x)==find(y+n) || find(x)==find(y+2*n)) ans++; else { merge(x,y); merge(x+n,y+n); merge(x+2*n,y+2*n); } } else { if(find(x)==find(y) || find(x)==find(y+n)) ans++; else { merge(x,y+2*n); merge(x+n,y); merge(x+2*n,y+n); } } } cout<<ans; return 0; } /* in: 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 out: 3 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/162165317
https://blog.csdn.net/hnjzsyjyj/article/details/146433179