并查集是一种树型的数据结构，用于处理一些**不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）**定义了两个用于此数据结构的操作：
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
算法实现
变量
一个数组parent代表第i个元素所指向的父节点
一个数组sz代表以i为根的集合中的元素个数 （用以优化算法，非必须）
1int* parent; // parent[i]表示第i个元素所指向的父节点
2
3// 使用sz还是rank优化需要根据题目的要求进行选择
4int* sz; // sz[i]表示以i为根的集合中元素个数
5int* rank; // rank[i]表示以i为根的集合所表示的树的层数
6
7int count; // 数据个数
函数
初始化
循环对每个元素的parent和sz赋值，此时每个元素都以自己为根节点，且集合中元素个数均为1
1parent = new int[count];
2sz = new int[count];
3this->count = count;
4for( int i = 0 ; i < count ; i ++ ){
5 parent[i] = i;
6 sz[i] = 1;
7}
Find函数
assert需要assert.h头文件，处理异常数据p
1// 查找过程, 查找元素p所对应的集合编号
2// O(h)复杂度, h为树的高度
3int find(int p){
4 assert( p >= 0 && p < count );
5 // 不断去查询自己的父亲节点, 直到到达根节点
6 // 根节点的特点: parent[p] == p
7 while( p != parent[p] )
8 p = parent[p];
9 return p;
10}
Union函数
寻找两个元素的根节点并将两个元素所在的集合合并
- 基于sz的优化
1// 合并元素p和元素q所属的集合
2// O(h)复杂度, h为树的高度
3void unionElements(int p, int q){
4
5 int pRoot = find(p);
6 int qRoot = find(q);
7
8 if( pRoot == qRoot )
9 return;
10
11 // 根据两个元素所在树的元素个数不同判断合并方向
12 // 将元素个数少的集合合并到元素个数多的集合上
13 if( sz[pRoot] < sz[qRoot] ){
14 parent[pRoot] = qRoot;
15 sz[qRoot] += sz[pRoot];
16 } else{
17 parent[qRoot] = pRoot;
18 sz[pRoot] += sz[qRoot];
19 }
20}
- 基于rank的优化
1// 合并元素p和元素q所属的集合
2// O(h)复杂度, h为树的高度
3void unionElements(int p, int q){
4
5 int pRoot = find(p);
6 int qRoot = find(q);
7
8 if( pRoot == qRoot )
9 return;
10
11 // 根据两个元素所在树的元素个数不同判断合并方向
12 // 将元素个数少的集合合并到元素个数多的集合上
13 if( rank[pRoot] < rank[qRoot] ){
14 parent[pRoot] = qRoot;
15 }else if( rank[qRoot] < rank[pRoot]){
16 parent[qRoot] = pRoot;
17 }else{ // rank[pRoot] == rank[qRoot]
18 parent[pRoot] = qRoot;
19 rank[qRoot] += 1; // 此时, 我维护rank的值
20 }
21}
isConnected函数
用于检测两个元素是否属于同一集合
1// 查看元素p和元素q是否所属一个集合
2// O(h)复杂度, h为树的高度
3bool isConnected( int p , int q ){
4 return find(p) == find(q);
5}
Count函数
如HDU-1232需要检测一共有几个集合
1int count_sets(){
2 int count = 0;
3 for(int i = 0; i < this->count; i++){
4 if(find(i) == i)
5 count++;
6 }
7 return count;
8}
完整算法
全部使用C++的类写的算法，使用方法如下
1int n;
2cin >> n;
3UF1::UnionFind uf = UF1::UnionFind(n);
也可以将其中的变量及函数放到min函数外面使用
基于sz优化
1#include <cassert>
2
3using namespace std;
4
5namespace UF1{
6
7 class UnionFind{
8
9 private:
10 int* parent; // parent[i]表示第i个元素所指向的父节点
11 int* sz; // sz[i]表示以i为根的集合中元素个数
12 int count; // 数据个数
13
14 public:
15 // 构造函数
16 UnionFind(int count){
17 parent = new int[count];
18 sz = new int[count];
19 this->count = count;
20 for( int i = 0 ; i < count ; i ++ ){
21 parent[i] = i;
22 sz[i] = 1;
23 }
24 }
25
26 // 析构函数
27 ~UnionFind(){
28 delete[] parent;
29 delete[] sz;
30 }
31
32 // 查找过程, 查找元素p所对应的集合编号
33 // O(h)复杂度, h为树的高度
34 int find(int p){
35 assert( p >= 0 && p < count );
36 // 不断去查询自己的父亲节点, 直到到达根节点
37 // 根节点的特点: parent[p] == p
38 while( p != parent[p] )
39 p = parent[p];
40 return p;
41 }
42
43 // 查看元素p和元素q是否所属一个集合
44 // O(h)复杂度, h为树的高度
45 bool isConnected( int p , int q ){
46 return find(p) == find(q);
47 }
48
49 // 合并元素p和元素q所属的集合
50 // O(h)复杂度, h为树的高度
51 void unionElements(int p, int q){
52
53 int pRoot = find(p);
54 int qRoot = find(q);
55
56 if( pRoot == qRoot )
57 return;
58
59 // 根据两个元素所在树的元素个数不同判断合并方向
60 // 将元素个数少的集合合并到元素个数多的集合上
61 if( sz[pRoot] < sz[qRoot] ){
62 parent[pRoot] = qRoot;
63 sz[qRoot] += sz[pRoot];
64 }
65 else{
66 parent[qRoot] = pRoot;
67 sz[pRoot] += sz[qRoot];
68 }
69 }
70 };
71}
基于rank优化
1#include <cassert>
2
3using namespace std;
4
5namespace UF2{
6
7 class UnionFind{
8
9 private:
10 int* rank; // rank[i]表示以i为根的集合所表示的树的层数
11 int* parent; // parent[i]表示第i个元素所指向的父节点
12 int count; // 数据个数
13
14 public:
15 // 构造函数
16 UnionFind(int count){
17 parent = new int[count];
18 rank = new int[count];
19 this->count = count;
20 for( int i = 0 ; i < count ; i ++ ){
21 parent[i] = i;
22 rank[i] = 1;
23 }
24 }
25
26 // 析构函数
27 ~UnionFind(){
28 delete[] parent;
29 delete[] rank;
30 }
31
32 // 查找过程, 查找元素p所对应的集合编号
33 // O(h)复杂度, h为树的高度
34 int find(int p){
35 assert( p >= 0 && p < count );
36 // 不断去查询自己的父亲节点, 直到到达根节点
37 // 根节点的特点: parent[p] == p
38 while( p != parent[p] )
39 p = parent[p];
40 return p;
41 }
42
43 // 查看元素p和元素q是否所属一个集合
44 // O(h)复杂度, h为树的高度
45 bool isConnected( int p , int q ){
46 return find(p) == find(q);
47 }
48
49 // 合并元素p和元素q所属的集合
50 // O(h)复杂度, h为树的高度
51 void unionElements(int p, int q){
52
53 int pRoot = find(p);
54 int qRoot = find(q);
55
56 if( pRoot == qRoot )
57 return;
58
59 // 根据两个元素所在树的元素个数不同判断合并方向
60 // 将元素个数少的集合合并到元素个数多的集合上
61 if( rank[pRoot] < rank[qRoot] ){
62 parent[pRoot] = qRoot;
63 }
64 else if( rank[qRoot] < rank[pRoot]){
65 parent[qRoot] = pRoot;
66 }
67 else{ // rank[pRoot] == rank[qRoot]
68 parent[pRoot] = qRoot;
69 rank[qRoot] += 1; // 此时, 我维护rank的值
70 }
71 }
72 };
73}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。