并查集概述
并查集(Union-Find)是一种用于处理集合关系的算法,在连通图的相关问题中非常实用。基本的操作包括集合的并(Union)和查找元素所属集合(Find)。
算法思路如下:每一个集合,都有一个代表元。在同一个集合中的所有元素,它们的代表元必然相同。要区分一个元素属于哪一个集合,找到它的代表元即可。
其存储结构通常为一个一维数组(N代表元素总数):1
int father[N + 1] = { 0 };
初始化如下:1
2
3
4
5
6
7
8
9
10
11
12
13for (int i = 1; i <= N; i++) {
father[i] = i;
}
```
那么根据定义,用于查找某个元素所在集合的代表元的函数可以这样实现:
```c++
int getFather(int x) {
if (father[x] == x) {
return x;
} else {
return getFather(father[x]);
}
}
但是,当元素数量很大,多次的递归显然效率较低。那么,可以引入“压缩路径”的方法:1
2
3
4
5
6
7
8
9
10int getFather(int x) {
if (father[x] == x) {
return x;
}
else {
int xFather = getFather(father[x]);
father[x] = xFather;
return xFather;
}
}
这样,在每一次递归之后,都会更新father[x]的值,实现了压缩路径的目的,避免了多次重复的递归。这种方式实现的并查集,时间复杂度为O(n)
。