并查集知识点汇总
基于id的并查集
思路：设置id数组，数组的每个元素是元素标识。初始化每个元素的值都不一样，如果值一样表示属于同一个集合内的元素。
实现：
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
| public class UnionFind {
private int[] id;
private int count;
public UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
int pid = find(p);
int qid = find(q);
if (pid == qid) {
return;
}
for (int i = 0; i < id.length; i++) {
if (find(i) == pid) {
id[i] = qid;
}
}
count--;
}
}
|
find()很快，但是union()很慢
基于parent的并查集
思路：不再使用id数组，而使用parent数组，定义为：parent[i]表示索引为i的节点的父节点的索引，初始时，每个元素都指向自己。
代码：
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
| public class UnionFind {
private int[] parent;
private int count;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (parent[p] != p) {
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
count--;
}
}
|
quick-union基于size的优化
思路：基于parent的并查集在给两个元素合并时没有考虑哪一个元素作为根，此时对于find会有影响。因此我们维护一个size数组，表示以该节点为根的元素个数，在union时将集合元素少的指向集合元素多的节点的根，会使形成的树层数较低。
代码：
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
| public class UnionFind {
private int[] parent;
private int count;
private int[] size;
public UnionFind(int n) {
count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int p) {
while (parent[p] != p) {
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (size[pRoot] > size[qRoot]) {
parent[qRoot] = pRoot;
size[pRoot] += size[qRoot];
} else {
parent[pRoot] = qRoot;
size[qRoot] += size[pRoot];
}
count--;
}
}
|
quick-union基于rank的优化
思路：使用rank数组存放以该节点为根的深度
代码：
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
| public class UnionFind {
private int[] parent;
private int count;
private int[] rank;
public UnionFind(int n) {
count = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int p) {
while (parent[p] != p) {
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = pRoot;
} else if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
} else {
parent[qRoot] = pRoot;
rank[pRoot]++;
}
count--;
}
}
|
quick-union基于路径压缩的非递归实现
并查集的一个特性是，只要元素是连在一起的，谁指向谁并不重要。
思路：路径压缩，在find的时候进行整理。
代码：
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
| public class UnionFind {
private int[] parent;
private int count;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
count--;
}
}
|
quick-union基于路径压缩的非递归实现
代码：
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
| public class UnionFind {
private int[] parent;
private int count;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (parent[p] != p) {
parent[p] = find(parent[p]);
}
return parent[p];
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
count--;
}
}
|
举个栗子🌰
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
| class Solution {
public int findCircleNum(int[][] M) {
UnionFind uf = new UnionFind(M.length);
for (int i = 0; i < M.length; i++) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && i != j) {
uf.union(i, j);
}
}
}
return uf.count;
}
class UnionFind {
private int[] parent;
private int count;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
count--;
}
}
}
|
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 boolean equationsPossible(String[] equations) {
UnionFind uf = new UnionFind(26);
for (String s : equations) {
if (s.charAt(1) == '=') {
int p = s.charAt(0) - 'a';
int q = s.charAt(3) - 'a';
uf.union(p, q);
}
}
for (String s : equations) {
if (s.charAt(1) == '!') {
int p = s.charAt(0) - 'a';
int q = s.charAt(3) - 'a';
if (uf.isConnected(p, q)) {
return false;
}
}
}
return true;
}
class UnionFind {
private int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
}
|
常见的二维坐标转化为一维坐标，此题关键在于将’0’合并到虚拟节点上
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
| class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
if (m < 1) {
return 0;
}
int n = grid[0].length;
int[][] directions = new int[][]{{1, 0}, {0, 1}};
int size = m * n;
UnionFind uf = new UnionFind(size + 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
for (int[] direction : directions) {
int newX = i + direction[0];
int newY = j + direction[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == '1') {
uf.union(getIndex(i, j, n), getIndex(newX, newY, n));
}
}
} else {
uf.union(getIndex(i, j, n), size);
}
}
}
return uf.count - 1;
}
private int getIndex(int x, int y, int cols) {
return x * cols + y;
}
class UnionFind {
private int[] parent;
private int count;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
count--;
}
}
}
|
参考：liwewei1419大佬的文章 高级数据结构：并查集
