并查集理论讲解和代码实现

一、概念

并查集是一种树形的数据结构，主要用于解决一些元素分组的问题。用于处理一些不相交集合的合并以及查询问题

并查集的思想是用一个数组表示了整片森林，树的根节点唯一标识了一个集合，我们只要找到了某个元素的树根，就能确定它在哪个集合里

二、并查集构建过程

我们先讲解一下并查集的构建过程

父   子
1     3
1     2
5     4
2     4
6     8
8     7
1
2
3
4
5
6
7

我们假设以上节点两两在一个集合中，左边为父节点，右边为子节点

对于前面四组数据，我们构造出如下的结构

这出现了问题，根据第4组数据构造集合时，应该把4所在树的根节点与2所在树的根节点相连，正确的集合构造如下：

构造并查集过程中，并不是简单的把两个节点相连，而是把节点所在的树的根节点相连

判断两个节点是否在一个集合中，判断这俩节点所在树的根节点是否相同即可

我们接着构造后两组数据的集合

上面这种直接把7放在8下面的做法是错误的，我们刚刚说了，合并两个集合是把两个树的树根节点进行合并。7单独成一棵树的根节点，和6进行合并，正确合并如下：

我们通过以上的构造过程，有如下总结：

• 构造并查集过程中，并不是简单的把两个节点相连，而是把节点所在的树的根节点进行相连（不关心根节点的父子关系）
• 判断两个节点是否在一个集合中，判断这俩节点所在树的根节点是否相同即可

三、代码实现

代码上实现时，无论是合并还是查询，都要找节点所在树的根节点，故需要记录父节点

主要思想：每一个节点对应的数组元素位置，存储它父节点的编号即可

怎么初始化？

由于我们说每个独立节点所在树的根节点就是自己，于是我们用它自己的节点编号进行初始化

什么时候找到树根了？

当x = arr[x]相等时，表示自己的父节点是自己，则表示树根是自己

并查集初始化如下：

我们构造的森林用并查集表示如下

遍历数组，通过比较元素值和下标是否相同即可得到并查集中有几个树根。从图中也可以看到，节点1和6就是树根了

#include <iostream>

using namespace std;

const int SIZE = 9;
int parent[SIZE];


// 返回x所在树的根节点的编号
int find_root(int x) {
	if (x <= 0 || x >= SIZE) {
		return -1;
	}
	while (x != parent[x]) {
		x = parent[x];
	}
	return x;
}

// 递归版本的查询
int cur_find_root(int x) {
	if (x <= 0 || x >= SIZE) {
		return -1;
	}
	if (x == parent[x]) {
		return x;
	}
	else {
		return cur_find_root(parent[x]);
	}
}

// 合并x和y所在的集合
void merge(int x, int y) {
	x = find_root(x);
	y = find_root(y);
	if (x != y) {
		// x和y在一个集合中则不需要合并，不在一个集合则需要合并
		parent[y] = x;
		// parent[x] = y;
	}
}

int main() {
	for (int i = 0; i < SIZE; i++) {
		parent[i] = i;
	}

	int x, y;
	for (int i = 0; i < 6; i++) {
		cin >> x >> y;
		merge(x, y);
	}
	cout<<(find_root(2) == find_root(8) ? "YES" : "NO")<<endl;
	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
44
45
46
47
48
49
50
51
52
53
54
55
56