并查集

Posted on

最近刷 leetcode 952 题，第一次知道并查集这个数据结构，来记录一下。

什么时候使用并查集？

当有许多节点在一起，你想要找到某一点以及和这一点相连以及间接相连的所有的点的时候，并查集就是最佳的数据结构之一。假设我们有下面这个图：

1
2
3
4
5
6
7
8
9
10
11
12
graph = {
    1: [],
    2: [1],
    3: [2],
    4: [2, 3],

    9: [6, 7],
    5: [9],
    6: [],
    7: [5],
    8: [5, 6, 9]
}

很容易看出：1, 2, 3, 4 是相连的；5, 6, 7, 8, 9 是相连的。如果我们想找到最大相连子图，那么并查集就排上用场了。

并查集的定义

一个并查集首先会定义一个 parent 数组，用来记录每一个点的最远的祖先节点，即下下标是节点的值，值是最远的祖先。 一个 find 函数，这个函数用来查找给定节点的最远的祖先的坐标。 一个 union 函数，这个函数接受两个节点（x 和 y）, 同时他会将 parent[y] 的值定为 parent[x] 的值，即将 y 的最远祖先的下标赋值给 parent[x]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y

例子

以我们上面的为例，我们想要找到最大连通子图的节点个数，怎么做？很简单。我们之需要对 graph 节点中每一个点和他的下一连接点做 union 操作就可以了。

1
2
3
4
5
union_find = UnionFind(max(graph.keys()) + 1)

for j, v in graph:
     for node in v:
          union_find.union(v, j)

我们来模拟运行上面的代码：首先，parent 数组经过初始化后为 parent[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，对于第一个节点parent[1]的值不会改变。第二点 2 会使得 parent[2] = 1。如此反复，parent的值会编程 parent = [0, 1, 1, 1, 1, 7, 7, 7, 7, 7]。

然后我们使用：

1
2
3
4
cnt = [0 for _ in range(max_val + 1)]
for num in A:
     cnt[union_find.find(num)] += 1
return max(cnt)

来统计哪一个数字出现的次数最多，结果是7，出现了5次。所以7所在的子图为最大连通子图，数目为5.

0%