【算法提高班】并查集

lucifer210

发布于 2020-02-26 13:57:54

4670

发布于 2020-02-26 13:57:54

文章被收录于专栏：脑洞前端

关于并查集的题目不少，官方给的数据是 30 道（截止 2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。这类题目如果掌握模板，那么刷这种题会非常快，并且犯错的概率会大大降低，这就是模板的好处。

我这里总结了几道并查集的题目：

547.朋友圈[1]
721. 账户合并[2]
990. 等式方程的可满足性[3]

大家可以学了模板之后去套用一下上面的三道题，做不出来的可以看看我的题解。

并查集概述

并查集算法，主要是解决图论中「动态连通性」问题的

Union-Find 算法解决的是图的动态连通性问题，这个算法本身不难，能不能应用出来主要是看你抽象问题的能力，是否能够把原始问题抽象成一个有关图论的问题。

如果你对这个算法不是很明白，推荐看一下这篇文章Union-Find 算法详解[4]，讲的非常详细。

你可以把并查集的元素看成部门的人，几个人可以组成一个部门个数。

并查集核心的三个方法分别是union, find, connected。

union: 将两个人所在的两个部门合并成一个部门（如果两个人是相同部门，实际山不需要合并）

（图来自 labuladong）

find: 查找某个人的部门 leader
connnected: 判断两个人是否是一个部门的

（图来自 labuladong）

模板

这是一个我经常使用的模板，我会根据具体题目做细小的变化，但是大体是不变的。

class UF:
    parent = {}
    cnt = 0
    def __init__(self, M):
        # 初始化 parent 和 cnt

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        self.parent[self.find(p)] = self.find(q)
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

如果你想要更好的性能，这个模板更适合你，相应地代码稍微有一点复杂。

class UF:
    parent = {}
    size = {}
    cnt = 0
    def __init__(self, M):
        # 初始化 parent，size 和 cnt

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
            # 路径压缩
            self.parent[x] = self.parent[self.parent[x]];
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        # 小的树挂到大的树上， 使树尽量平衡
        leader_p = self.find(p)
        leader_q = self.find(q)
        if self.size[leader_p] < self.size[leader_q]:
            self.parent[leader_p] = leader_q
        else:
            self.parent[leader_q] = leader_p
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

大家可以根据情况使用不同的模板。