并查集

算法常见题之并查集或者不相交集合数据结构 DSU，当有一组集合 n 个元素，假设我们经常需要：（1）判定某个元素属于哪个集合，（2）将两个集合合并成一个集合。那么，我们只需要维护一个并查集即可。

为什么不直接在每个元素对象中添加一个描述从属集合的属性呢？因为合并时，时间复杂度是 O(n)，而并查集只需要很少时间。

分析

并查集包含三种操作，创建集合，合并两个集合，查找元素的从属集合。我们一般会从一个集合中挑出一个代表元素来代表整个集合，如果把集合看作一棵树，那么查找操作可以看作是查找根节点，而合并操作则可以看作是将一棵树的根节点指向另一棵树的根节点。

模板代码

模版代码（使用了路径压缩）：

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def union(self, x, y):
        self.pa[self.find(x)] = self.find(y)

启发式合并

启发式合并是对上面代码的改进，简单来说，如果我们每次都将深度或者点数更小（二选一）的集合树连接到一棵更大的集合树下，那么之后的查找操作时间将会缩短。

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))
        self.size = [1] * size

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
            self.pa[y] = x
            self.size[x] += self.size[y]

一般来说，用压缩路径即可。Tarjan 证明了如果不使用启发式合并、只使用路径压缩的最坏时间复杂度是 $O (m \log n)$，而姚期智 证明了不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 $O (m\alpha (m,n))$。

CLRS 的阅读攻略😂 在学习章节之前可以先看看这个总结，节约时间，搞清楚重点。

问题

547. 省份数量

1319. 连通网络的操作次数