【扩展域并查集】
● 并查集的两个核心操作 find 及 merge 代码
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;
● 扩展域并查集
扩展域并查集是一种高效处理多关系问题的数据结构，通过扩展元素的逻辑域来维护复杂关系，适用于传统并查集无法解决的场景。缺点是需扩展多倍数组，空间占用较高。
（1）逻辑域扩展
为每个元素创建多个逻辑域（如“同类”、“猎物”、“天敌”等），每个域表示元素在不同关系中的状态（或称身份）。
例如，在食物链问题中，每个动物需拆分为 3 个逻辑域（同类域、捕食域、被食域）。其中：
同类域：表示与自身同类的集合。
捕食域：表示自身捕食的动物集合，即猎物集合。
被食域：表示自身天敌的集合。当声明 x 捕食 y 时，需通过合并操作建立以下逻辑：
x 的捕食域与 y 的同类域合并 → 表示 x 的猎物是 y 的同类。
y 的被食域与 x 的同类域合并 → 表示 y 的天敌是 x 的同类。
x 的被食域与 y 的捕食域合并 → 确保 y 的捕食对象是 x 的天敌，形成闭环。
之所以这样执行合并的底层逻辑是食物链的循环依赖。其遵循环形结构（如 A→B→C→A）。
又如，二分图检测问题（k=2）中，每个元素的逻辑域分为 0（同类域）、1（对立域）。
当声明 x 是 y 的敌人时，需通过合并操作建立以下逻辑：
x 的对立域与 y 的同类域合并 → 表示 x 的敌人是 y 的同类。
y 的对立域与 x 的同类域合并 → 表示 y 的敌人是 x 的同类。
（2）父数组
在扩展域并查集中，父数组是用于维护所有逻辑域合并关系的核心数据结构。它通过为每个元素的不同逻辑域分配独立的索引，并记录这些域的父节点，从而支持复杂关系（如对立、层级、依赖等）的高效建模和查询。
（3）关系映射
在扩展域并查集中，父数组的大小为 n×k，其中 n 是元素总数，k 是每个元素的逻辑域数。其关系映射规则为“编号为 idx 的元素的第 i 个域的索引为 idx+i×n”，其中 idx∈[0, n-1]，i∈[0, k-1]。
例如，食物链问题（k=3）中，每个元素的逻辑域分为0（同类域）、1（捕食域）、2（被食域）。则：
若元素总数 n=5，则父数组大小为 n×k=5×3=15，对应索引为 0~14。
元素 0 的域：0+0×5=0（同类域）、0+1×5=5（捕食域）、0+2×5=10（被食域）。
元素 1 的域：1+0×5=1（同类域）、1+1×5=6（捕食域）、1+2×5=11（被食域）。
元素 2 的域：2+0×5=2（同类域）、2+1×5=7（捕食域）、2+2×5=12（被食域）。
元素 3 的域：3+0×5=3（同类域）、3+1×5=8（捕食域）、3+2×5=13（被食域）。
元素 4 的域：4+0×5=4（同类域）、4+1×5=9（捕食域）、4+2×5=14（被食域）。
显然，在食物链问题（k=3）中，元素 u 的同类域索引为 u+0×n=u，元素 u 的捕食域索引为 u+1×n=u+n，元素 u 的被食域索引为 u+2×n=u+2n。其中，u 为元素的编号。
若 x 与 y 是同类，则执行 merge(x,y)、merge(x+n,y+n)、merge(x+2*n,y+2*n)。
若 x 吃 y，则执行 merge(x,y+2*n)、merge(x+n,y)、merge(x+2*n,y+n)。
又如，二分图检测问题（k=2）中，每个元素的逻辑域分为 0（同类域）、1（对立域）。
若元素总数 n=3，则父数组大小为 n×k=3×2=6，对应索引为 0~5。
元素 0 的域：0+0×3=0（同类域）、0+1×3=3（对立域）。
元素 1 的域：1+0×3=1（同类域）、1+1×3=4（对立域）。
元素 2 的域：2+0×3=2（同类域）、2+1×3=5（对立域）。
显然，在二分图检测问题（k=2）中，元素 u 的同类域索引为 u+0×n=u，元素 u 的对立域索引为 u+1×n=u+n。其中，u 为元素的编号。
若 x 与 y 是同类，则执行 merge(x,y)。
若 x 吃 y，则执行 merge(x+n,y)、merge(y+n,x)。
● 扩展域并查集的合并操作
扩展域并查集的合并操作通过多域交叉关联实现复杂关系维护，其核心是将元素的多个逻辑状态拆分为独立域进行管理。合并前，需将每个逻辑域的父结点初始化为自身。以下是不同场景下的合并规则详解：
（1）同类关系合并
规则：若元素 x 和 y 属于同类，需合并两者的所有对应逻辑域。
操作示例（食物链问题）：合并 x 的同类域与 y 的同类域、合并 x 的捕食域与 y 的捕食域、合并 x 的被食域与 y 的被食域。
逻辑意义：确保同类元素的全部状态一致。
（2）对立关系合并
规则：若元素 x 和 y 对立，需交叉合并 x 的同类域与 y 的对立域，反之亦然。
操作示例（二分图检测）：合并 x 的同类域 与 y 的对立域、合并 y 的同类域 与 x 的对立域。
逻辑意义：维护对立双方阵营的严格隔离。
（3）层级关系合并
规则：若元素 x 对 y 存在单向依赖（如捕食、领导关系），需跨域合并。
操作示例（食物链中 x 吃 y）：合并 x 的捕食域 与 y 的同类域、合并 x 的同类域 与 y 的被食域、合并 x 的被食域 与 y 的捕食域。
逻辑意义：形成循环依赖链，避免逻辑矛盾。
【“扩展域并查集”模板题】
洛谷 P1892：[BalticOI 2003] 团伙：
#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int pre[maxn];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,m;cin>>n>>m;for(int i=1; i<=2*n; i++) pre[i]=i; //2*nchar ch;int x,y;while(m--) {cin>>ch>>x>>y;if(ch=='F') merge(x,y);else merge(x+n,y), merge(y+n,x);}int ans=0;for(int i=1; i<=n; i++) {if(find(i)==i) ans++;}cout<<ans<<endl;return 0;
}/*
in:
6
4
E 1 4
F 3 5
F 4 6
E 1 2out:
3
*/
【参考文献】