文章目录
  1. 1. 并查集概念
  2. 2. 模板
    1. 2.1. find
    2. 2.2. Union
  3. 3. 例题
    1. 3.1. Friend Circles
    2. 3.2. Number of Islands

并查集概念

并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。

  • 查询元素a和元素b是否属于同一组。
  • 合并元素a和元素b所在的组。

模板

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
class DisjointSets{
private:
vector<int> parent, rank;

public:
DisjointSets(int num) {
parent = vector<int>(num, 0);
rank = vector<int>(num, 0);
for (int i = 0; i < num; i++) {
parent[i] = i;
}
}

int find(int p) {
if(p == parent[p])
return p;
parent[p] = find(parent[p]);
return parent[p];
}

void unionTwo(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootQ] > rank[rootP]) {
parent[rootP] = rootQ;
}else {
parent[rootQ] = rootP;
if (rank[rootP] == rank[rootQ]) {
rank[rootP]++;
}
}
}

};

Disjoint Sets (以下简称DS)的本质是许多棵树。每个圈子里的元素都组成了一棵树。然而我们的表示方法并不是用常规tree node的方法记录的,而是用数组.

DS里面拥有一个大小为N的vector parent,对于parent[i],存储着第i号元素所属圈子的老大。DS里面的另一个vector rank用来存储树的高度,它的作用会在Union操作中体现出来。

DS里面经典的两个操作分别是find和Union.

find

find就是寻找这个圈子的老大(这棵树的root)。对于find来说,在寻找root的过程中,我们不仅要找到root,还要把沿途经过的所有node的parent都变成root,也就是把自己和沿途所有的node都变成root的孩子(同时也变成了深度为1的leaf)。这个操作叫path compression,意义在于下次我们如果寻找这些node的老大,就可以一步到位了(直接通过parent[i]找到root)。这对时间复杂度的优化是非常重要的。

Union

Union是什么?是我们知道了两个元素属于同一个圈子。如果我们的DS已经知道这一点,那么没问题,如果我们的DS不知道这一点,我们要告诉它。并且很重要的是,这里不是针对两个元素,而是要把这两个元素所处的两个圈子融合成一个圈子,这也就是Union叫法的由来。那么我们分别用find找到两个元素所处tree的root,然后通过比较rank[root]的大小看哪棵树更大。最后我们把小的那棵树的root变成大的那棵树的root的孩子。之所以要选择把小的那棵树融合进大的那棵树,是因为我们希望让树的孩子的高度都尽量小。假设小的树的孩子数量是N1,大的树的孩子数量是N2。如果把小数融合进大树,那么我们让N1个node的高度都增加了1,反之我们要让N2个node的高度都增加1。后者明显是违反我们希望让树的孩子的高度都尽量小这个意愿的。
Disjoint Sets using union by rank and path compression Graph Algorithm中以具体的例子演示了Union的过程。

例题

Friend Circles

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
class Solution {
public:
class DisjointSets{
private:
vector<int> parent, rank;
int count;

public:
DisjointSets(int num) {
count = num;
parent = vector<int>(num, 0);
rank = vector<int>(num, 0);
for (int i = 0; i < num; i++) {
parent[i] = i;
}
}

int find(int p) {
if(p == parent[p])
return p;
parent[p] = find(parent[p]);
return parent[p];
}

void unionTwo(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
count -= 1;
if (rank[rootQ] > rank[rootP]) {
parent[rootP] = rootQ;
}else {
parent[rootQ] = rootP;
if (rank[rootP] == rank[rootQ]) {
rank[rootP]++;
}
}
}

int getCount() {
return count;
}

};
int findCircleNum(vector<vector<int>>& M) {
DisjointSets ds(M.size());
for (int i = 0, n = M.size(); i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (M[i][j]) ds.unionTwo(i, j);
}
}
return ds.getCount();
}
};

对于整个matrix,如果M[i][j]为1,我们则需要告诉DS i和j属于一个圈子。这里因为对称性,我们只需要遍历半个matrix就可以得到所有信息。在DS里面我增加了一个count。count代表现在DS中独立圈子的数量。因为最开始我们什么信息都不知道,假设每个人都属于自己的独立圈子,所以count为人的个数,之后每一次Union操作,如果我们发现i和j所处圈子(的老大)不同(root1 != root2),那么说明有两个圈子要合并成一个,那么就少了一个圈子,所以count要减1.最后我们返回count,也就是圈子的数量。

Number of Islands

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
public:
class DisjointSets{
private:
vector<int> parent, rank;
int count;

public:
DisjointSets(int num) {
count = num;
parent = vector<int>(num, 0);
rank = vector<int>(num, 0);
for (int i = 0; i < num; i++) {
parent[i] = i;
}
}

int find(int p) {
if(p == parent[p])
return p;
parent[p] = find(parent[p]);
return parent[p];
}

void unionTwo(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
count -= 1;
if (rank[rootQ] > rank[rootP]) {
parent[rootP] = rootQ;
}else {
parent[rootQ] = rootP;
if (rank[rootP] == rank[rootQ]) {
rank[rootP]++;
}
}
}

int getCount() {
return count;
}

};

int numIslands(vector<vector<char>>& grid) {

if(grid.size() == 0 || grid[0].size() ==0)
return 0;
int m = grid.size();
int n = grid[0].size();
int num = 0;
unordered_map<int, int> hashMap;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(grid[i][j] == '1'){
hashMap[i*n+j] = num;
num++;
}
}
}

DisjointSets ds(num);

for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(grid[i][j] == '1'){
if(i - 1 >= 0 && hashMap.count((i-1)*n+j)){
ds.unionTwo(hashMap[(i-1)*n+j], hashMap[i*n+j]);
}
if(i + 1 < m && hashMap.count((i+1)*n+j)){
ds.unionTwo(hashMap[(i+1)*n+j], hashMap[i*n+j]);
}
if(j - 1 >= 0 && hashMap.count(i*n+j-1)){
ds.unionTwo(hashMap[i*n+j-1], hashMap[i*n+j]);
}
if(j + 1 < n && hashMap.count(i*n+j+1)){
ds.unionTwo(hashMap[i*n+j+1], hashMap[i*n+j]);
}
}
}
}
return ds.getCount();

}
};

参考资料:

  1. 超有爱的并查集~
  2. Disjoint Sets using union by rank and path compression Graph Algorithm
  3. Disjoint Sets / Union Find
  4. Union Find Kruskal’s Algorithm
文章目录
  1. 1. 并查集概念
  2. 2. 模板
    1. 2.1. find
    2. 2.2. Union
  3. 3. 例题
    1. 3.1. Friend Circles
    2. 3.2. Number of Islands