问题的提出
给定一个大小为n的集合{a, b, c, f, ...}，其中存在k <= n个连通块，将该集合分成k个小的子集。
给定两个元素i，j，如何在尽可能高效地进行以下两个操作
- 判断两个元素是否在同一个连通块（即两元素连同）
- 将两个元素所在的连通块连载一起，形成一个连通块
问题的解决
并查集，能在均摊O(1)的时间复杂度内解决上面的问题。
使用C++最简易的实现如下：
Init(n) { for(int i = 0; i < n; ++i) root[i] = i;}
Find(x) { return x == root[x] ? x : root[x] = find(root[x]); }
Union(x, y) {root[find(x)] = find(y); }
技巧一：路径压缩
如下的代码实现了路径压缩操作。
Find(x) { return x == root[x] ? x : root[x] = find(root[x]); }
[!question] 怎么理解路径压缩？
针对集合{1,2,3,4,5,6}，若存在两个连通块：{1,2,3,4}，{5,6}。其中{1,2,3,4}的存储形式是graph RL4 --> 3 --> 2 --> 1当调用
Find(4)时，调用过程如下，1<-2<-3<-4 F(4) := root[4] = F(3) = 1 F(3) := root[3] = F(2) = 1 F(2) := root[2] = F(1) = 1 F(1) := 1最终，连通块会变成下面这个样子
graph RL4 --> 13 --> 12 --> 1
技巧二：按秩归并
秩，是指连通块的大小。
TODO
完整代码
class UnionFind:def __init__(self, n: int):# 一开始有 n 个集合 {0}, {1}, ..., {n-1}# 集合 i 的代表元是自己，大小为 1self._fa = list(range(n)) # 代表元self._size = [1] * n # 集合大小self.cc = n # 连通块个数# 返回 x 所在集合的代表元# 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元def find(self, x: int) -> int:# 如果 fa[x] == x，则表示 x 是代表元if self._fa[x] != x:self._fa[x] = self.find(self._fa[x]) # fa 改成代表元return self._fa[x]# 判断 x 和 y 是否在同一个集合def is_same(self, x: int, y: int) -> bool:# 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合# 这就是代表元的作用：用来快速判断两个元素是否在同一个集合return self.find(x) == self.find(y)# 把 from 所在集合合并到 to 所在集合中# 返回是否合并成功def merge(self, from_: int, to: int) -> bool:x, y = self.find(from_), self.find(to)if x == y: # from 和 to 在同一个集合，不做合并return Falseself._fa[x] = y # 合并集合。修改后就可以认为 from 和 to 在同一个集合了self._size[y] += self._size[x] # 更新集合大小（注意集合大小保存在代表元上）# 无需更新 _size[x]，因为我们不用 _size[x] 而是用 _size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 _size[x]self.cc -= 1 # 成功合并，连通块个数减一return True# 返回 x 所在集合的大小def get_size(self, x: int) -> int:return self._size[self.find(x)] # 集合大小保存在代表元上# 作者：灵茶山艾府
# 链接：https://leetcode.cn/discuss/post/mOr1u6/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。