并查集 Union Find
并查集是为了实现等价类的一种数据结构，基本操作有：Union 和 Find
好像说了个废话。
并查集有多种实现
- 基于数组
- 核心思想：构建一个数组，每一位记录该位元素的代表元
- 基于矩阵
- 核心思想：等价是一个二元关系，矩阵自然可以表达二元关系
- 基于根数
- 这个最有潜力，也是我们讨论的重心。
- 核心思想：同根的一个树是一个等价类，union 就把树挂到另一个树上，find 就是寻父的一个过程。
- 容易想到，构造一个尽量平衡的树有利于降低我们操作序列的时间复杂度。这也是后面讨论的重点。
UnionFind¶
有权图（加权的并），路径压缩查找
- 加权并：尽量将节点多的树作为被挂的，节点少的作为挂的，这样有利于树尽量平衡
- 路径压缩：即 find 时，将所有节点直接挂到 root 上，这样能尽量降低树的高度，提高最坏情况下的 find 效率
- \(makeSet()\): \(\Theta(\log ^{*} (n+1))\)
- \(wUnion\)：\(\Theta(1)\)
- \(cFind\):：\(\Theta(2\log ^{*}(n+1))\) 结论：将一个集合转化为并查集，需要的 link operations \(\in O((n+m)\log ^{*}n)\) \(\log ^{*}n\) 几乎是常数级别 \(n\) 是元素个数，\(m\) 是集合个数。