理论

联合查找数据结构提供以下操作：

• make_sets(n) 使用 n 单例初始化 union-find 数据结构
• find(i) 返回元素 i 的代表
• union(i,j) 合并包含 i 和 j 的集合

我们通过存储代表我们 0 到 n - 1 元素的分区父的每一个元素 i 最终导致元素 parent[i] 代表含 i 集。
如果一个元素本身是一个代表，那么它就是它自己的父元素，即 parent[i] == i。

因此，如果我们从单件集开始，每个元素都是它自己的代表：

我们可以通过简单地遵循这些父指针来找到给定集合的代表。

现在让我们看看如何合并集合：
如果我们想要合并元素 0 和 1 以及元素 2 和 3，我们可以通过将父级 0 设置为 1 并将父级设置为 2 来实现：

在这种简单的情况下，只需更改元素父指针本身。
如果我们想要合并更大的集合，我们必须始终更改要合并到另一个集合的集合的代表的父指针 ：在合并(0,3)之后，我们设置了集合的代表的父节点包含 0 到包含 3 的集合的代表

为了使示例更有趣，我们现在也合并(4,5)，(5,6)和(3,4) ：

我要介绍的最后一个概念是路径压缩 ：
如果我们想要找到一个集合的代表，我们可能必须在到达代表之前遵循几个父指针。我们可以通过将每个集的代表直接存储在其父节点中来使这更容易。我们失去了合并元素的顺序，但可能会有很大的运行时间增益。在我们的例子中，唯一未压缩的路径是从 0,4 和 5 到 3 的路径：