并查集

定义

并查集是一种树形的数据结构,用来表示不相交集合的数据。并查集中的每个子集是一棵树,每个元素是某棵树中的一个节点。树中的每个节点有一个指向父节点的指针,树的根节点的指针指向它自己。

合并和查找

并查集支持两种操作,即合并和查找。合并操作将两个子集合并成一个集合,只需要将一个子集对应的树的根节点的指针指向另一个子集对应的树的根节点。

另一种操作是查找,即确定某个元素v处于哪个子集中。并查集中的子集由对应的树的根节点代表。从元素v对应的节点开始沿着指向父节点的指针一直找到树的根节点,即节点的祖先节点。并查集的查找操作经常用来判断两个元素是否属于同一个子集。如果两个元素的祖先节点相同,那么它们属于同一个子集。

存储形式

并查集元素存储形式采用数组表示法。因为并查集所有的操作只需要维护元素对父节点的指向,所以存储形式采用一个数组pre[x]=a来存储,其中x代表当前元素,a代表x元素的父节点。

并查集的优化技巧

  • 路径压缩
  • 按秩合并

leetcode 200 岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。


输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3

代码

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
# -*- coding:utf-8 -*-
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0])
self.count = 0 # 节点数
# 用一维数组存储
self.parent = [-1] * (m * n)
# 存储最大层数 秩
self.rank = [0] * (m * n)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
self.parent[i * n + j] = i * n + j
self.count += 1

def find(self, i):
# 查找如果是自己就说明本身是代表元,如果不是自己就往前查找直到找到代表元
if self.parent[i] != i:
# 路径压缩
self.parent[i] = self.find(self.parent[i])
return self.parent[i]

def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
# 按秩合并
if self.rank[rootx] < self.rank[rooty]:
rootx, rooty = rooty, rootx
self.parent[rooty] = rootx
if self.rank[rootx] == self.rank[rooty]:
self.rank[rootx] += 1
self.count -= 1

def getCount(self):
return self.count


class Solution:
def numIslands(self, grid) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
uf = UnionFind(grid)
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
grid[r][c] = "0"
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
uf.union(r * nc + c, x * nc + y)

return uf.getCount()