并查集（Disjoint Set）

大家好，欢迎来到IT知识分享网。

目录

1.定义

2.初始化

3.查找

4.合并

4.1.按秩合并（启发式合并）

5.例题

题目描述

输入格式

输出格式

输入输出样例

说明/提示

1.定义

并查集，也称为不相交集合数据结构，是一种用于管理元素分组以及查找元素所属组的数据结构。

在并查集中，每个集合通常用一棵树来表示，其中树的根节点代表集合的代表元素。通过查找操作可以找到元素所属的集合，而通过合并操作可以将两个集合合并为一个集合。

顾名思义，并查集支持两种操作：

• 合并（Union）：合并两个元素所属集合（合并对应的树）
• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

注意：并查集无法以较低复杂度实现集合的分离。

2.初始化

用一个数组dsu[x]来存x的父节点。

例如：

此时dsu[1] = 1，dsu[6]=3等；

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树，方便起见，最开始每个元素的父节点为自己。

void init(int* fa) { for (int i = 1; i <= N; i++)fa[i] = i; }

3.查找

根节点时集合的代表，查找就是找到元素所在集合的根。

int find(int x) { if (fa[x] == x) return x; return find(fa[x]); }

如果链式很长这种查找会很耗时，我们可以在返回的同时，将fa[x]的值修改为根节点，即将各节点的父节点都修改为根节点，也叫带路径的查找（路径压缩），这样可以加快以后的查找进程。

int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); }

4.合并

把一个集合的根节点指向另一个集合的根节点。

void unionset(int x, int y) {//将x的根节点指向y的根节点 fa[find(x)] = find(y); }

在并查集中，将小集合的根节点指向大集合的根节点是一种优化策略，通常结合了按秩合并的思想。这个优化策略有助于保持并查集的平衡性，避免树过深，从而提高查找和合并操作的效率。以下是这种优化策略的一些优点：

1. 平衡性： 将小树合并到大树上可以保持并查集的平衡性。通过始终将高度较小的树合并到高度较大的树上，可以避免出现极端情况下树的高度过高，从而降低了查找操作的时间复杂度。
2. 减小树的高度： 通过将小树合并到大树上，可以减小整个并查集中树的高度。较低的树高度意味着在进行查找操作时需要遍历的节点数量更少，提高了查找操作的效率。
3. 降低时间复杂度： 通过维护平衡的树结构，查找和合并操作的平均时间复杂度可以更接近于O(1)，提高了整体的操作效率，减小树的高度可以减少下一次查询时的递归次数。
4. 避免退化： 如果不进行优化，当按照树的深度进行合并时，可能会出现树的退化情况，即树的高度过高，导致操作的效率下降。

4.1.按秩合并（启发式合并）

把小集合的根节点指向大集合的根节点。

void unionset(int x, int y) { x = find(x); y = find(y); if (x == y)return;//在同一个集合不用合并 if (siz[x] > siz[y])swap(x, y);//如果x的大小大于y的大小，交换，让x表示大集合，y表示小集合 fa[x] = y;//再将x指向y siz[y] += siz[x]; }

算法竞赛按秩合并不常用，因为路径压缩足够好了，不用再用空间换时间。

5.例题

洛谷：P3367 【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数  。

当  = 1 时，将 ​ 与  所在的集合合并。

当  = 2 时，输出  与  是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个  = 2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例

输入 #1复制

4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4

输出 #1复制

N Y N Y 

说明/提示

对于 30% 的数据，N≤10，M≤20。

对于 70% 的数据，N≤100，M≤。

对于 100% 的数据，1≤N≤，1≤M≤2×，1≤​,≤N，∈{1,2}。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 10001; int fa[N]; int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } void unionset(int x, int y) { fa[find(x)] = find(y); } void f(int x, int y) { if (find(x) == find(y))cout << "Y" << endl; else cout << "N" << endl; } void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) fa[i] = i; int z, x, y; while (m--) { cin >> z >> x >> y; if (z == 1) { unionset(x, y); } else f(x, y); } } int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); solve(); return 0; }