什么是并查集?

并查集是一种用于快速在元素之间建立集合关系,并且快速判断两个元素是否属于同一集合的数据结构。其基于的基本假设是传递性:如果元素xxyy属于同一集合,并且yyzz也属于同一集合,那么元素xxzz一定属于同一集合。针对满足这种性质的集合问题,并查集就是一种极其快速的解决方式。

数据结构

并查集基于树的数据结构,每一棵树代表一个集合,每棵树的根节点可以视为这个集合的代表元素。当需要建立新的元素之间的关系时,例如建立aabb的关系,就将bb所在的树作为子树加入aa所在的树中。检查两个元素是否属于同一集合,只需要检查两个元素所在的子树的根节点是否相同即可。

代码实现

以下是并查集的简单代码实现。

具体实现中,我们可以针对每一个元素维护一个parent指针指向其父元素,为方便起见,我们规定:如果一个元素的父节点是它本身,那么该节点就是一棵树的根节点。初始情况下:每个元素自己构成一个集合(即每个元素自己就构成一棵树)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# include<bits/stdc++.h>
using namespace std;

class UnionFindSet {
private:
vector<int> parent;

public:
UnionFindSet(int n) {
this->parent = vector<int>(n, 0);
for(int i = 0; i < n; i++) {
this->parent[i] = i;
}
}

};

接下来,我们需要完成查找某个结点所在的树的根节点的函数int find(int x){}。这个实现是简单的,可以使用循环,也可以使用递归。在这里,我们使用递归的方式来实现之。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class UnionFindSet {
private:
vector<int> parent;

int find(int x) {
if(x >= n || x < 0) return -1;
return x == parent[x] ? x : find(parent[x]);
}

public:
// UnionFindSet(int n) {
// ...
// }

};

这里将其作为私有成员函数的原因是,调用方并不需要知道我们如何维护并查集,find函数也因此只会被我们使用到而已。

接下来就是剩余的附加关系的函数void set_union(int x, int y){}和判断是否属于同一集合的函数bool is_unioned(int x, int y){}。有了find函数,这两个函数的实现就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UnionFindSet {
private:
vector<int> parent;

int find(int x) {
return x == parent[x] ? x : find(parent[x]);
}

public:
// UnionFindSet(int n) {
// ...
// }

void set_union(int x, int y) {
parent[find(y)] = find(x);
}

bool is_unioned(int x, int y) {
return find(x) == find(y);
}

};

时间优化

可以看到,上述实现的并查集的时间开销都集中在find操作上,而find操作的时间复杂度又取决于树的深度。因此,有没有方法可以降低树的深度呢?答案是,在进行find操作时,我们可以将路径上访问过的结点的父节点直接设为最后find结果所代表的根节点。这样,进行一次查找后,被访问过的路径的parent就直接指向了根节点,使得树的深度降低为11。修改find函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class UnionFindSet {
private:
vector<int> parent;

int find(int x) {
if(x >= n || x < 0) return -1;
- return x == parent[x] ? x : find(parent[x]);
+ return x == parent[x] ? x : parent[x] = find(parent[x]);
}

public:
// UnionFindSet(int n) {
// ...
// }

};
完整代码
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
class UnionFindSet {
private:
vector<int> parent;

int find(int x) {
return x == parent[x] ? x : parent[x] = find(parent[x]);
}

public:
UnionFindSet(int n) {
this->parent = vector<int>(n, 0);
for(int i = 0; i < n; i++) {
this->parent[i] = i;
}
}

void set_union(int x, int y) {
parent[find(y)] = find(x);
}

bool is_unioned(int x, int y) {
return find(x) == find(y);
}

};
- -