什么是并查集?
并查集是一种用于快速在元素之间建立集合关系,并且快速判断两个元素是否属于同一集合的数据结构。其基于的基本假设是传递性:如果元素x x x 和y y y 属于同一集合,并且y y y 与z z z 也属于同一集合,那么元素x x x 与z z z 一定属于同一集合。针对满足这种性质的集合问题,并查集就是一种极其快速的解决方式。
数据结构
并查集基于树的数据结构,每一棵树代表一个集合,每棵树的根节点可以视为这个集合的代表元素。当需要建立新的元素之间的关系时,例如建立a a a 与b b b 的关系,就将b b b 所在的树作为子树加入a a a 所在的树中。检查两个元素是否属于同一集合,只需要检查两个元素所在的子树的根节点是否相同即可。
代码实现
以下是并查集的简单代码实现。
具体实现中,我们可以针对每一个元素维护一个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 : };
这里将其作为私有成员函数的原因是,调用方并不需要知道我们如何维护并查集,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 : 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
就直接指向了根节点,使得树的深度降低为1 1 1 。修改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); } };