【包含例题P1955、P1892、P2024、P1196】并查集、扩展域并查集、带权并查集
并查集
基础并查集就像管理多个独立的家族，每个家族有一个族长（根节点）。主要解决两大问题：
找族长（Find）：查询某个成员属于哪个家族，每一个家族都有一个族长做代表。
联姻（Union）：把两个家族合并成一个大家族
关键特性
路径压缩：查询时把查找路径上的成员直接指向族长，加快后续查询
比喻
想象公司部门合并
初始时每个员工自成一个部门（父节点指向自己）
当合并两个部门时，指定一个总负责人
查询某员工所属部门时，会沿着汇报关系找到最终负责人
适用场景
网络连通性检测
朋友圈关系计算
最小生成树算法（Kruskal）
P1955 [NOI2015] 程序自动分析
题解
//离散化 + 并查集
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
int n;
struct node
{int x,y,e;
}a[N];
//离散化
int disc[N * 2]; //要对x，y离散化，所以要开两倍的大小
int pos;
unordered_map<int,int> mp;
//并查集
int fa[N * 2];int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}void un(int x,int y)
{fa[find(x)] = find(y);
}bool issame(int x, int y)
{return find(x) == find(y);
}bool solve()
{//离散化 cin >> n;//清空数据 (清空pos和mp)pos = 0;mp.clear();for(int k=1;k<=n;k++){cin >> a[k].x >> a[k].y >> a[k].e;disc[++pos] = a[k].x;disc[++pos] = a[k].y;}sort(disc + 1, disc + 1 + pos);int cnt = 0;for(int i=1;i<=pos;i++){int t = disc[i];if(mp.count(t)) continue;cnt++;mp[t] = cnt;}//初始化并查集 for(int i=1;i<=cnt;i++) fa[i] = i;//先遍历数组，执行所有合并操作 for(int i=1;i<=n;i++){int x = a[i].x, y = a[i].y, e = a[i].e;if(e == 1){un(mp[x],mp[y]);}}for(int i=1;i<=n;i++){int x = a[i].x, y = a[i].y, e = a[i].e;if(e == 0){if(issame(mp[x],mp[y])) return false;}}return true;
}int main()
{int T; cin >> T;while(T--){if(solve()) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}
扩展域并查集
在基础并查集上增加"平行宇宙"概念，每个元素有两个分身：
主分身（原域）
影子分身（扩展域）
通过两个域之间的关系表达更复杂的连接性：
朋友关系：主分身与主分身相连
敌对关系：主分身与对方的影子分身相连
关键特性：
双倍空间：需要2倍原始空间存储扩展关系
关系传递：A与B敌对，B与C敌对 ⇒ A与C是朋友
比喻
我们先搞懂正常的朋友，敌人关系是怎样表示的。这里面难理解的就是为什么朋友关系只需要连一下，敌人关系却需要连两下，我们下面就用狼人杀来比喻。
就像狼人杀游戏：
朋友域：村民阵营
敌人域：狼人阵营
当两个玩家互相指认时：
朋友关系就是互相证明是村民，只需要一条线；
敌对关系就是互相指控是狼人，需要互相指控对方的狼人身份，即它在敌人域的映射。敌对关系是需要两者同时认为的，当方面的认为不构成敌人关系，所以在实现的时候，不要忘了要连两条线。
适用场景
生物链关系（A吃B，B吃C，C吃A）
二分图检测
敌对网络分析
例题
1. P1892 [BalticOI 2003] 团伙
分析
首先明确，并查集中体现关系的就只有一个核心操作就是合并（或者通俗点叫连线），这个合并只有一个意义，那就是表示被合并的两个集合/元素（单个元素的集合），他们的性质相同。扩展域并查集中，那些被扩展出来的部分，都是用来表示原本1 ~ n个元素的不同身份。在这题中，连线只能表达他们的性质相同，即朋友关系，不能通过直接连线表达他们是敌人，分析这个测试用例，数据范围n=6，则与 1 ~ 6 相连的都表示与 1 ~ 6 是朋友关系，7 ~ 12 是敌人域，分别表示 1 ~ 6 的敌人，与 7 ~ 12 相连的也表示与 7 ~ 12 是朋友关系，但是它就是 1 ~ 6 的敌人。如何表达敌人关系？那就是与 1 ~ 6 在敌人域中对应的数字连线，1 ~ 6 的敌人域，天生就是 1 ~ 6 的敌人，它们被设计出来就是为了表达敌人关系。举个例子，1是4的敌人，那么我不能直接给1和4连线来表示他俩是敌人，因为连线只能表示他俩是朋友，那么我就将1和10（4的敌人）连线，表示1和4的敌人是朋友，那么1就和4是敌人；再将4和7（1的敌人连线），表示4和1的敌人是朋友，那么4就和1是敌人。这样以来目的就达到了，要注意的是要考虑所有的情况，就比方说不能只将1和10连线，而忽略要将4和7连线。
题解
#include <iostream>
using namespace std;
const int N = 1010;
int fa[N * 2]; //扩展域并查集，两倍的数据范围用来处理敌人关系
int n,m;int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}void un(int x,int y)
{fa[find(y)] = find(x); //一定要让朋友域（1~n）做父节点
}int main()
{cin >> n >> m;for(int i=1;i<=n*2;i++) fa[i] = i; //初始化 while(m--){char opt;int p,q;cin >> opt >> p >> q;if(opt == 'F'){un(p,q);}else{un(p,q+n);un(q,p+n);}}int ret = 0;for(int i=1;i<=n;i++){if(fa[i] == i) ret++;}cout << ret;return 0;
}
2. P2024 [NOI2001] 食物链
题解
#include<iostream>
using namespace std;
const int N = 5e4 + 10;
int fa[N * 3];
int n,k;
int ret;int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}void un(int x,int y)
{fa[find(x)] = find(y);
}bool issame(int x,int y)
{return find(x) == find(y);
}//bool check(int op,int x,int y)
//{
// if(x > n || y > n) return false;
// if(op == 1 && !issame(x,y)) return false; //不能直接写issame，如果他们之间还没有分配任何关系，这时候指定他们为同类不应该是假话
// if(op == 2 && issame(x,y) || op == 2 && find(x) == find(y + n)) return false;
// return true;
//}bool check(int op,int x,int y)
{if(x > n || y > n) return false;if(op == 1) //x、y同类 {//举反例 x吃y || y吃x if(find(x) == find(y+n) || find(x) == find(y+2*n)) return false; } if(op == 2) //x吃y {//举反例 同类 || y吃x if(find(x) == find(y) || find(x) == find(y + n)) return false;} return true;
}int main()
{cin >> n >> k;//用并查集一进来就要初始化，扩展域并查集初始化全部范围 for(int i=1;i<=n*3;i++) fa[i] = i;while(k--){int op,x,y;cin >> op >> x >> y;if(!check(op,x,y)) {ret++;continue;}if(op == 1){ un(x,y);un(x+n,y+n);un(x+2*n,y+2*n);}else{un(x,y+2*n);un(x+n,y);un(x+2*n,y+n);}}cout << ret; return 0;
}
带权并查集
在基础并查集的基础上，给每个节点到父节点的连接赋予"权值"，通过路径压缩和合并时的权值调整，维护节点间的相对关系。
关键特性：
权值累积：查找时累加路径上的权值
关系推导：合并时根据输入关系推导新的权值关系
相对性：只能维护节点间的相对关系，无法获取绝对数值
带权并查集没有一个固定的模板，要理解思路，随机应变。注意根据问题需求明确“方向性”。
例如带权并查集中常见的查询操作query是返回d[x] - d[y]还是d[y] - d[x]要根据具体问题设计。
权值维护公式
find操作中：
fa[N]表示当前元素的父节点
d[N]表示当前元素到父节点的路径长（权值）
查找时：d[x] += d[fa[x]]
union操作中：
rootX表示x所在集合的根节点
w表示x、y之间的距离（权值）
合并时：d[rootX] = d[y] - d[x] + w
比喻
就像公司薪资体系：
每个员工记录自己与直接上级的薪资差
当查询某员工与CEO的薪资差时，需要累加整条汇报链的差值
当两个部门合并时，需要重新调整CEO的薪资差，因为合并就是将CEO（根节点）归到另一个部门的CEO（根节点）的手下，这时候就要更改原CEO到现在CEO的薪资差
适用场景
等式方程求解（A/B=2, B/C=3 ⇒ A/C=6）
向量关系维护
模运算关系计算
例题
1. P2024 [NOI2001] 食物链
这道题同样可以使用带权并查集来解决。在上面的扩展域并查集中，我们是通过与不同的域连接来判断关系；在带权并查集中，我们是通过权值差来判断关系。
题解
#include<iostream>using namespace std;const int N = 5e4 + 10;int fa[N]; //并查集
int d[N]; //权值 int n,k;int find(int x)
{if(fa[x] == x) return x;int t = find(fa[x]); //路径压缩，配合return fa[x] = t;会使父节点挂在根节点下 d[x] += d[fa[x]]; //权值改变 return fa[x] = t;
}//带权并查集的合并是需要知道要合并的两个集合之间的权值
void un(int x,int y,int w)
{int fx = find(x),fy = find(y);if(fx != fy){fa[fx] = fy;d[fx] = w + d[y] - d[x];}
}int main()
{cin >> n >> k;for(int i=1;i<=n;i++) fa[i] = i;int ret = 0;//带权并查集是通过权值差来判断关系 while(k--){int op,x,y; cin >> op >> x >> y;if(x > n || y > n) ret++;else if(op == 1) //同类 {//判断假话，不是同类 if(find(x) == find(y) && ((d[y]-d[x]) % 3 + 3) % 3 != 0) ret++;else un(x,y,0); //是真话就要维护并查集 }else //x吃y {if(find(x) == find(y) && ((d[y]-d[x]) % 3 + 3) % 3 != 1) ret++;else un(x,y,2);}}cout << ret;return 0;
}
2. P1196 [NOI2002] 银河英雄传说
题解
#include<iostream>using namespace std;const int N = 3e4 + 10;
int n = 3e4;
int fa[N]; //维护合并集合
int d[N]; //维护权值
int cnt[N]; //维护每个根节点上的元素长度 int find(int x)
{if(fa[x] == x) return x;int t = find(fa[x]);d[x] += d[fa[x]]; //维护权值 return fa[x] = t; //压缩路径
} void un(int x,int y)
{int fx = find(x), fy = find(y);if(fx != fy) //判断x和y不在一个集合才可以合并 {fa[fx] = fy;d[fx] = cnt[fy];cnt[fy] += cnt[fx];}
}int query(int x,int y)
{int fx = find(x), fy = find(y);if(fx != fy) return -1;else return abs(d[y] - d[x]) - 1;
}int main()
{int T; cin >> T;for(int i=1;i<=n;i++){fa[i] = i;cnt[i] = 1;}while(T--){char op; int x,y;cin >> op >> x >> y;if(op == 'M'){un(x,y); }else{cout << query(x,y) << endl;}}return 0;}