Union Find-并查集

并查集简介

并查集（Union Find）用于判断各个不相交集合中某元素是否存在，可以以接近常数级的时间复杂度完成查找操作。它适用于图的连通性判断、最近公共祖先等问题，通常用森林数组来实现。

基本操作

并查集有两个核心操作：查找（find）和合并（union）。

• 查找：从集合中判断元素 x 是否存在（属于哪个集合）。
• 合并：若两个集合不相交，则可以执行合并操作。通常的做法是将高度低的树合并到高度高的树上，以控制树的高度。

初始化时，每个元素各自构成一个单独的集合，之后不断引入关系，将相关集合合并在一起。

问题引入

若某个家族人员过于庞大，要判断两个成员是否是亲戚，确实不容易。给出某个亲戚关系图，求任意两个人是否具有亲戚关系。规定：若 x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚；若 x、y 是亲戚，则 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。

简单来看，问题就是判断两个元素 x、y 在这张庞大的关系网络中是否存在亲戚关系。每个成员都可以看作一个独立元素，若用常规图论的深度优先搜索来做，代价比较大。并查集非常适合处理这类查找与判断问题。

数组表示与操作示例

可以通过 hash 来简化这一过程：元素按照 1234567 来区分，对应数组下标 0123456，数组中存储的内容是该元素的父节点，表示该元素与其父节点存在亲戚关系。

初始化时，数组的初始存储值是其本身下标，表示各元素之间暂无关系。

初始数组为 0123456，其中 456 属于第二个集合。

• 输入 ab，数组变为 0023456，1 的父节点是 0，表示他们是亲戚关系。
• 输入 bd，数组变为 0021456，3 的父节点是 1，他们是亲戚关系。
• 输入 ac，数组变为 0001456，2 的父节点是 0。
• 第一组集合输入完毕，开始处理第二组集合。
• 输入 ef，数组变为 0001446。
• 输入 fg，数组变为 0001445。

上述输入描述的是数组的合并操作，对应的代码实现如下。