概述
并查集是一种非常高效的查找算法，它多用于元素分组的问题。它主要包含两种操作，第一种是合并集合（并），第二种是查找两个元素是否属于同一集合（查）。
并查集的重要思想在于用集合中的一个元素代表集合。并查集的底层结构类似于堆，利用数组来存储一个树的结构。但不同的是，堆是一棵独立的二叉树，并查集的树是多叉树，而且可能不止一棵树(也就是森林)。在并查集中，我们把相互独立的数据集称为连通分量，连通分量在逻辑上可以形象地描述为一棵树，每棵树都有一个根节点，其他的元素都会直接或间接指向根节点。
举个例子，例如这个数组：[0,2,2,2,0,1]，对应下标为0-5。这个数组称作parent数组，即存储父节点。初始化时a[i]=i，即每个节点的父亲都是自己（或者说每个节点都是孤立的）。随后经过一系列的合并操作，我们的数组最终从孤立的点结构形成了树结构。
（图片来自https://segmentfault.com/a/1190000022952886）
以第一棵树为例，5的父节点是1，故a[5]=1，然后1的父节点是2，则a[1]=2（a[a[5]]=2)，2是根节点，故a[2]=2（a[a[a5]]]=2）最后，数组每个元素都代表其指向的父节点。
实现（c语言实现）
并查集的实现代码非常的简短和精妙。这里先给出最基本的一种实现：
1
2
3
4
5
6
7
8
9
10
11
| int fa[MAXN];
void init(int n) {
for(int i = 0; i < n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
else return find(fa[x]);
}
void union(int x, int y) {
fa[find(x)] = fa[find(y)];
}
|
这种写法可以说是非常精简了。但是这种写法导致的问题是，find操作的效率较低，因为随着合并操作的进行，整个并查集可能会形成一个链的结构，从叶节点查询到父节点的时间复杂度就会升高。
这里有两种优化方法。一个是优化find，一个是优化union。优化find可以考虑路径压缩，即将路径上的每个节点的父节点都指向根节点。优化union可以考虑按秩合并（秩在这里可以理解为树的深度，初始化所有元素的秩为1）。
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
| int fa[MAXN];
int rank[MAXN];
void init(int n) {
for(int i = 0; i < n; i++) {
fa[i] = i;
rank[i] = 1;
}
}
int find(int x) {
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) return;
if(rank[rootX] <= rank[rootY]) {
fa[rootX] = rootY;
} else {
fa[rootY] = rootX;
}
if(rank[rootX] == rank[rootY] && x != y) rank[rootY]++;
}
|
举例
亲戚问题
（洛谷P1551）亲戚
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出格式
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
这个题很明显的就是并查集问题。每一行读取亲戚关系的时候，就将两个亲戚合并入并查集；每一行查找两个人是否是亲戚关系（有相同的根节点）的时候，就分别执行查找操作查找其根节点并比较结果。
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
44
45
46
47
48
49
50
51
| #include <stdio.h>
#define MAXN 5001
int fa[MAXN];
int rank[MAXN];
void init(int n) {
for(int i = 1; i <= n; i++) {
fa[i] = i;
rank[i] = 1;
}
}
int find(int x) {
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) return;
if(rank[rootX] <= rank[rootY]) {
fa[rootX] = rootY;
} else {
fa[rootY] = rootX;
}
if(rank[rootX] == rank[rootY] && x != y) rank[rootY]++;
}
int main(){
int m, n, p;
scanf("%d %d %d", &n, &m, &p);
init(n);
for(int i = 0; i < m; i++) {
int Mi, Mj;
scanf("%d %d", &Mi, &Mj);
union(Mi, Mj);
}
for(int i = 0; i < p; i++) {
int Pi, Pj;
scanf("%d %d", &Pi, &pj);
if(find(Pi) == find(Pj)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
|