定义

From Introduction to Disjoint Set (Union-Find Algorithm) - GeeksforGeeks

Disjoint Set

Two sets are called disjoint sets if they don’t have any element in common,the intersection of sets is a null set

Disjoint Set Data Structure

A data structure that stores non overlapping or disjoint subset of elements is called disjoint set data structure. The disjoint set data structure supports following operations:

  • Adding new sets to the disjoint set.
  • Merging disjoint sets to a single disjoint set using Union operation.
  • Finding representative of a disjoint set using Find operation.
  • Check if two sets are disjoint or not.

实现

参考数据结构教程（C++语言描述）（第2版·微课视频版）

方式选择

选择树结构来实现，将并查集看做一个森林，每个等价类（即disjoint set）用一个棵树表示，并且通常选用根结点作为这个等价类的代表

下面内容仍然来自Introduction to Disjoint Set (Union-Find Algorithm) - GeeksforGeeks

Data Structures used are:
Array: An array of integers is called Parent[]. If we are dealing with N items, i’th element of the array represents the i’th item. More precisely, the i’th element of the Parent[] array is the parent of the i’th item. These relationships create one or more virtual trees.

Tree: It is a Disjoint set. If two elements are in the same tree, then they are in the same Disjoint set. The root node (or the topmost node) of each tree is called the representative of the set. There is always a single unique representative of each set. A simple rule to identify a representative is if ‘i’ is the representative of a set, then Parent[i] = i. If i is not the representative of his set, then it can be found by traveling up the tree until we find the representative.

存储结构

实际上是森林的双亲存储结构

1
2
int parent[MAXN];    //并查集存储结构
int rnk[MAXN];      //存储结点的秩（近似于高度）

（秩并不与高度完全相同，但它和高度呈正比）

Init

初始化时置所有结点的秩为0

Find

查找即找到x结点所属集合的根节点（判断条件：根节点的根节点是自己，即parent[y] = [y]）,这种查找是通过parent[x]向上找双亲实现的，显然树的高度越小查找性能越好。

所以在查找过程中会进行路径压缩，即把查找路径上的结点逐一指向根节点

Union

合并，即根据提供的等价关系(x,y)，将x和y所属的子树合并为一颗子树。

  1. 首先查找两结点所属子树的根节点rx和ry，若rx == ry，说明他们同属一颗子树，无需合并，否则需要合并
  2. 合并过程是对根结点的合并
    1. rnk[rx] < rnk[ry]，则将高度较小的rx结点作为ry的孩子结点，ry子树的高度不变
    2. rnk[rx] > rnk[ry]，则将高度较小的ry结点作为rx的孩子结点，rx子树的高度不变
    3. rnk[rx] = rnk[ry]，则均可，合并后子树高度增加1

代码

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
#include<iostream>
using namespace std;

const int MAXN = 100;

int parent[MAXN];
int rnk[MAXN];

void Init(){
    for(int i = 1; i <= MAXN; i++){
        parent[i] = i;
        rnk[i] = 0;
    }
}

//recursive
// int Find(int x){
//     if(x != parent[x]){
//         parent[x] = Find(parent[x]);
//     }
//     return parent[x];
// }

//non-recursive
int Find(int x){
    int rx = x;
    //第一遍循环，用来找到x的根节点
    while(parent[rx] != rx){
        rx = parent[rx];
    }
    //第二遍循环，用来路径压缩
    int y = x;
    while(y != rx){
        int tmp = parent[y];
        parent[y] = rx;
        y = tmp;
    }
    return rx;
}

void Union(int x, int y){
    int rx = Find(x);
    int ry = Find(y);
    if(rx == ry){
        return;
    }
    if(rnk[rx] < rnk[ry]){
        parent[rx] = ry;
    }else{
        if(rnk[rx] == rnk[ry]){
            rnk[rx]++;
        }
        parent[ry] = rx;
    }
}

插曲

在编写代码的时候，我用rank为数组命名，出现如下错误
reference to 'rank' is ambiguousgcc
解答如下：
c++11 - reference to ‘rank’ is ambiguous - Stack Overflow