并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（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
| class UnionFind {
int[] root = null;
public UnionFind()
root = new int[row*col];
for(int i=0;i<row*col;i++) {
root[i] = i;
}
}
public int find(int x) {
if(x==root[x]) {
return root[x];
}
return find(root[x]);
}
public void union(int x,int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX!=rootY) {
root[rootX] = rootY;
}
}
}
|
Leetcode.547 省份数量
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
| import java.util.HashSet;
import java.util.Set;
class Solution {
int[] root = null;
public int findCircleNum(int[][] isConnected) {
Set<Integer> set = new HashSet<>();
int n = isConnected.length;
root = new int[n];
for (int i = 0; i < n; i++) {
root[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && isConnected[i][j] == 1) {
union(i, j);
}
}
}
for (int num : root) {
set.add(find(num));
}
return set.size();
}
int find(int x) {
if (root[x] == x) {
return root[x];
}
return find(root[x]);
}
void union(int x, int y) {
int xx = find(x);
int yy = find(y);
if (xx != yy) {
root[xx] = yy;
}
}
}
|
番外
岛屿问题也可以使用并查集Union Find，但深度搜索写起来更爽