408数据结构-并查集 自学知识点整理

前置知识：树与森林

---

并查集的概念

并查集是一种简单的集合表示，它支持以下$3$种操作：
$1)$ $Initial(S)$：将集合$S$中的每个元素都初始化位只有一个单元素的子集合。
$2)$ $Union(S,Root1,Root2)$：把集合$S$中的子集合$Root2$并入子集合$Root1$。要求$Root1$和$Root2$互不相交，否则不执行合并。
$3)$ $Find(S,x)$：查找集合$S$中单元素$x$所在的子集合，并返回该子集合的根结点。

简而言之，就是一种支持“合并”和“查找”的“集合”，其中“合并”是指将两个集合合并为一个集合，“查找”就是查找某个元素所在的集合。

并查集的存储结构

通常用树的双亲表示法作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲域为负数（通常设为该子集合元素数量的相反数）。
在采用树的双亲指针数组作为并查集的存储表示时，集合元素的编号从$0$到$SIZE-1$，其中$SIZE$是最大的元素个数。

并查集的基本实现

并查集的结构定义如下：

#define SIZE 100
int UFSets[SIZE];//集合元素数组（双亲指针数组）
1
2

初始化：

void Init(int S[]) {//初始化
	memset(S, -1, sizeof(S));
	//数组各元素初值置-1，表示每个单元自成集合，这个memset等价于下面的写法
	/*
	for (int i = 0; i < SIZE; ++i)
		S[i] = -1;
	*/
	return;
}
1
2
3
4
5
6
7
8
9

$Find$操作：（查）

int Find(int S[], int x) {//“查”操作，找到x所属集合（返回x所属树的根结点）
	while (S[x] >= 0)//循环查找x的根
		x = S[x];
	return x;//根的S[]小于0
}
1
2
3
4
5

判断两个元素是否属于同一集合，只需分别找到它们的根作比即可。

$Union$操作：（并）
将两个不同集合的元素合并到同一集合，只需先分别找到它们的根，再令其中一棵子树根结点的双亲指向另一棵子树的根结点即可。

void Union(int S[], int Root1, int Root2) {
	//“并”操作，将两个集合合并为一个
	if (Root1 != Root2)S[Root2] = Root1;
	//若Root1和Root2是两个不同的集合，则将根Root2连在另一根Root1下面
	return;
}
1
2
3
4
5
6

$Find$操作的时间复杂度为$O(d)$，其中$d$为数的深度。
$Union$操作的时间复杂度为$O(1)$。

并查集实现的优化

极端情况下，$n$个元素构成的集合树深度为$n$，则$Find$操作的最坏时间复杂度为$O(n)$。
可以从$Union$操作下手，改进方法是：在合并之前，先判断两棵子树中结点的数量，令结点数少的子树根结点指向结点数多的子树根结点，即将小树合并到大树，为此需要用根结点的双亲域存放子树中的结点数以便比较。
代码实现如下：

void Union_(int S[], int Root1, int Root2) {//改进后的“并”操作
	if (Root1 == Root2)return;//同一集合无需合并
	if (S[Root2] > S[Root1]) {//若Root2结点数更少
		S[Root1] += S[Root2];//累加集合树的结点总数
		S[Root2] = Root1;//小树合并到大树
	}
	else {//Root1结点数更少
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12

采用这种方法构造的集合树，其深度不超过$\lfloor {\log }_{2}n\rfloor +1$。
但是当$n$很大的时候，随着子集逐对合并，集合树的深度还是会越来越大。为了进一步减少确定元素所在集合的时间，可以对$Find$操作再进一步优化，这就是大名鼎鼎的 “路径压缩”。
其思想就是，将查找路径上的所有元素都变成根的孩子，让树“变矮”，具体实现如下：

int Find_(int S[], int x) {//改进后的“查”操作
	int root = x;
	while (S[root] >= 0)root = S[root];//循环找到根
	while (x != root) {//路径压缩
		int t = S[x];//t指向x的父结点
		S[x] = root;//将x直接挂到根结点下
		x = t;//继续向上
	}
	//这个while循环也可以等价为下面这个for循环
	//for (int t; x != root; t = S[x], S[x] = root, x = t);
	return root;//返回根
}
1
2
3
4
5
6
7
8
9
10
11
12

通过对$Find$操作进行“压缩路径”的优化后，可使集合树的深度不超过$O(a(n))$，其中$a(n)$是一个增长极其缓慢的函数，对于常见的正整数$n$，通常$a(n)\le 4$。

完整代码可以看我的Github：传送门

---

附：洛谷P3367 【模板】并查集

题目描述

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

输入格式

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

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

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

输出格式

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

样例 #1

样例输入 #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
2
3
4
5
6
7
8

样例输出 #1

N
Y
N
Y
1
2
3
4

提示

对于 $30\%$ 的数据，$N\le 10$，$M\le 20$。

对于 $70\%$ 的数据，$N\le 100$，$M\le 10^3$。

对于 $100\%$ 的数据，$1\le N\le 10^4$，$1\le M\le 2\times 10^5$，$1\le X_i,Y_i\le N$， Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi​∈{1,2}。

这题还是我19年打$OI$的时候写的，总的来说是一个非常简单的板子题，直接套前面的基本操作即可，甚至不需要$Union$的优化。
不过我打$OI$时的码风是喜欢玩花里胡哨，见谅。

以下为100pts的代码：

#pragma GCC optimize(2) //手动O2
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 10005;
int n,m;
int fa[N];

inline int qread(){//快读（效果等于scanf和cin）
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*w;
}

inline int find(int x){//递归实现“查”操作，同时路径压缩
	return x==fa[x] ? x : fa[x]=find(fa[x]);
}

int main(){
    n=qread(),m=qread();
    for(int i=1;i<=n;++i)fa[i]=i;//初始化双亲数组，所有元素的双亲指向自身
    while(m--){
    	int z=qread(),x=qread(),y=qread();
    	int fx=find(x),fy=find(y);//查x，y的双亲
    	if(z==1){
    		if(fx!=fy)fa[fx]=fy;//直接合并
		}else if(z==2){
			if(fx==fy)putchar('Y');//同一集合输出Y
			else putchar('N');//否则输出N
			putchar('\n');
		}
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

对408考研初试，要求掌握并查集的相关概念，存储结构和代码实现。
不过，比起$OI$来说，408学的真的很浅。
以上。
（第五章终于结束了:）