并查集

本文介绍并查集的相关知识。

并查集的使用场景

并查集的使用场景如下图。我们有一些集合，每个集合有一个标识（如下图中的A,B,T）。现在我们有一个元素x，我们需要知道x在哪个集合中。

上述场景介绍了并查集的查。并查集的并指：将两个集合并起来。可以详细解释为：

1. 我们将新元素y添加到一个集合Y中。
2. 我们将新元素y添加到元素z的那个集合。
3. 合并元素y所在的集合与集合Z。
4. 合并元素y所在的集合与元素z所在的集合。

我们进一步思考下这些需求。首先1``2中所谓的新元素y，我们可以将其看作一个新集合Y'，其中仅包含一个元素y。这样1``2需求可以合并进3``4。另一方面，实际中往往没有明确的集合标识，故我们主要应对需求4即可。

综上，并查集主要实现find和union两个方法，python模板如下：

class UnionFind:
    def __init__(self):
        pass

    def find(self, x):
        if x not in any sets:
            create a new set
        else:
            find the set id

    def union(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        combine X and Y

实现并查集的方式

集合法

一种直观的实现方式是用set实现。对于每个集合，我们定义一个set，另外将所有的set存储起来。代码如下

class UnionFind:
    def __init__(self):
        self.all_set = []

    def find(self, x):
        for i, s in enumerate(self.all_set):
            if x in s:
                return i
        new_set = set([x])
        self.all_set.add(new_set)
        return len(self.all_set) - 1

    def union(self, x, y):
        xi = self.find(x)
        yi = self.find(y)
        if xi == yi:
            return xi
        elif xi < yi:
            Y = self.all_set.pop(yi)
            X = self.all_set.pop(xi)    
        else:
            X = self.all_set.pop(xi)
            Y = self.all_set.pop(yi)
        self.all_set.append(X | Y)
        return len(self.all_set) - 1

分析一下时间复杂度。在集合中查找元素为 $O(1)$ 。查询时，复杂度为 $O(\text{集合个数})$。合并时，复杂度也为 $O(\text{集合个数})$。另外列表的操作也很费时。

标志法

对每个元素分配一个集合标识。查找时，只需返回集合标识。合并时，将其中一个集合标识赋给另一个集合中每个元素。

class UnionFind:
    def __init__(self):
        self.val2id = dict()
        self.id2vallist = dict()
        self.n = 0

    def find(self, x):
        if x not in self.val2id:
            self.val2id[x] = self.n
            self.id2vallist[self.n] = [x]
            self.n += 1
        return self.val2id[x]

    def union(self, x, y):
        xi = self.find(x)
        yi = self.find(y)
        if xi != yi:
            listy = self.id2vallist.pop(yi)
            for i in listy:
                self.val2id[i] = xi
            self.id2vallist[xi].extend(listy)
        return xi

分析一下时间复杂度。查询时，复杂度为 $O(1)$。合并时，复杂度也为 $O(\text{集合中元素数量})$。

森林法

我们用树表示每个集合。在传统的树中，我们仅保存根节点，当检索元素时，需要从根节点遍历整棵树。为了加速，我们使用逆向查找的方式，即从中间节点查找根节点。如此，根节点也成为集合标识。为了实现这种查找方式，我们需要用哈希表存储每个节点的父节点。这样我们可以在 $O(1)$ 时间找到节点的父节点。

代码如下：

class UnionFind:
    def __init__(self):
        self.all_node = dict()

    def find(self, x):
        if x not in self.all_node:
            self.all_node[x] = x
        while self.all_node[x] != x:
            x = self.all_node[x]
        return x

    def union(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        if X == Y:
            return X
        else:
            self.all_node[Y] = X
            return X

在合并时，我们找到两个根节点。这时可以根据需求选择将哪个根节点作为新的根节点。比如，我们希望标识为树中最小元素，则新根为两个根的较小值。

分析一下时间复杂度。查找为 $O(\text{树的节点个数})$，并为 $O(\text{树的节点个数})$。

LeetCode

LeetCode包含一个并查集题单：https://leetcode-cn.com/tag/union-find/problemset/

但该题单中，有部分习题用回溯搜索解答更方便。下面是适合使用并查集的习题：

• 1971. 寻找图中是否存在路径：我的解答
• 684. 冗余连接：我的解答
• 面试题 17.07. 婴儿名字：我的解答
• 839. 相似字符串组：我的解答
• 399. 除法求值：我的解答

相关阅读

• VScode配置Python开发环境
• 红黑树