并查集 (Union-Find Disjoint Sets, 简称UFDS)

1. Introduction

The Union-Find Disjoint Sets (UFDS) data structure is used to model a collection of disjoint sets, which is able to efficiently (i.e., in nearly constant time) determine which set an item belongs to, test if two items belong to the same set, and union two disjoint sets into one when needed. It can be used to find connected components in an undirected graph, and can hence be used as part of Kruskal's algorithm for the Minimum Spanning Tree (MST) problem.

Note that this data structure has another alternative name: Disjoint Sets Union (DSU).

2. 可视化

在此查看并查集可视化的例子！
每棵树代表一个不相交的集合（因此多个不相交集合能形成一个森林），树的根是这个不相交集合的代表项目。

现在停下来看看当前可视化中的树。总共有多少项（N）？有多少个不相交的集合？每个不相交集的成员是什么？每个不相交集的代表项是什么？

2-1. 检查点1

由于我们固定了这个电子讲座的默认例子，你的答案应该是。N=13，有4个不相交的集合。{0,1,2,3,4,10}, {5,7,8,11}, {6,9}, {12}，下划线的成员是他们自己不相交集合的代表项。

2-2. 储存数据 - 第一部分

我们可以简单地用一个数组 p 记录这个树的森林，数组的大小为 N 个项目，其中 p[i] 记录了项目 i 的父节点，如果 p[i] = i，那么 i 就是这棵树的根，也是包含项目 i 的集合的代表项目。

再次看看上面的可视化，确定这个数组 p 中的值。

讨论：如果 i 是包含它的树的根，我们可以设置 p[i] = -1 而不是 p[i] = i 吗？这有什么影响？

2-3. 含义

[This is a hidden slide]

2-4. 检查点2

在同一个固定的例子上，你的答案应该是p=[1，3，3，3，5，6，5，5，6，4，8，12]，大小N=13，范围从p[0]到p[12]。

你可以检查一下，p[3]=3，p[5]=5，p[6]=6，p[12]=12，这与{3,5,6,12}是（它们自己的不相交集）代表项的事实一致。

2-5. 储存数据 - 第二部分

我们还在同样大小为N的数组rank中记录额外的等级信息。rank[i]的值是根植于顶点i的子树高度的上限，它将被用作UnionSet(i, j)操作的启发式指导。你会注意到，在 "路径压缩 "（将在后面描述）压缩某些路径后，rank值不再反映该子树的真实高度。

由于有很多项的等级为0，我们对可视化进行了如下设置，以减少杂乱：只有当顶点i的等级大于0时，VisuAlgo才会在顶点i下面以红色文字显示rank[i]的值（简写为一个字符r）。

2-6. 检查点3

在同一个固定的例子上，验证{1,4,6,8}的等级为1，{3,5}的等级为2，其余的等级为0（未显示）。

在这个时间点上，所有的等级值都是正确的，也就是说，它们确实描述了根在该顶点的子树的高度。我们很快就会看到，在接下来的几张幻灯片中，它们并不总是正确的。

3. 操作

此可视化页面中有五个可用的合并集操作：
示例，Initialize（N）（初始化），FindSet（i）（查找），IsSameSet（i，j）（在同一集），和UnionSet（i，j）（合并）。
第一个操作（示例）并不重要：具有各种特殊特征的合并集结构实例列表，供您参考。此e-Lecture模式始终使用“四个不相交集(Four disjoint sets)”示例作为起点。
另请注意，没有一个例子包含 "非常高 "的树。在我们描述了所使用的两种启发式方法之后，你很快就会明白其中的原因。

4. Initialize(N, M)

Initialize(N, M)：创建 N 个项目并用这些 N 个项目形成 M 个不相交的集合。我们随机选择两个不相交的集合并合并它们，直到我们有 M 个随机不相交的集合。由于使用了按秩合并的启发式方法和随机性，初始化过程很不可能创建一个高树。

默认形式是 Initialize(N, N)，即 M = N，所有的 p[i] = i 和 rank[i] = 0（所有这些秩值最初都不显示）。这个操作的时间复杂度显然是 O(N)。

由于屏幕大小的限制，我们设置 1 ≤ N ≤ 32。显然 M ≤ N。

5. FindSet（i）

FindSet（i）：从顶点i，递归地在树上往上移动。也就是说，从顶点i，我们转到顶点p [i]），直到我们找到该树的根，这是该不相交集的的代表项（代表项具有p [i] = i的性质）。

在这个FindSet（i）操作中，我们在每次调用FindSet（i）之后使用路径压缩，因为现在沿着从顶点i到根的路径的每个顶点都知道根是它们的代表项，并且可以用O(1)时间直接指向它。

5-1. 实践案例

如果我们执行 FindSet(12)，我们将立即得到顶点 12。
如果我们执行 FindSet(9)，我们将在 1 步后得到顶点 6，没有其他变化。

现在尝试执行 FindSet(0)。如果这是你在这个默认的 UFDS 示例上的第一次调用，它将在 2 步后返回顶点 3，然后由于路径压缩在行动，修改底层的 UFDS 结构（即，顶点 0 直接指向顶点 3）。注意，rank[1] = 1 的 rank 值现在是错误的，因为顶点 1 成为了一个新的叶子。然而，我们不会去更新它的值。

注意，下次你再次执行 FindSet(0) 时，它将会（更）快，因为路径已经被压缩了。现在，我们假设 FindSet(i) 的运行时间为 O(1)。

6. IsSameSet(i, j)

IsSameSet（i，j）：只需检查是否 FindSet（i） == FindSet（j）。该函数经常出现在Kruskal的MST算法中。由于它只调用FindSet操作两次，我们假设它的时间复杂度为O（1）。

请注意，FindSet函数在IsSameSet函数内部被调用，因此也间接使用了路径压缩。

6-1. 实践案例

如果我们调用IsSameSet(3, 5)，我们应该得到false，因为顶点3和顶点5是它们各自不相交集合的代表项，它们是不同的。

现在在相同的默认例子上尝试IsSameSet(0, 11)，看看顶点0和顶点11的间接路径压缩。我们应该得到false，因为两个代表项：顶点3和顶点5，是不同的。注意，现在顶点{1，5，8}的等级值是错误的。但我们不会修复它们。

7. UnionSet(i, j)

UnionSet(i, j)：如果项目 i 和 j 最初来自两个不相交的集合，我们将较短树/不相交集合的代表项目链接到较高树/不相交集合的代表项目（否则，我们什么也不做）。这也是在 O(1) 中完成的。

这是按秩合并启发式在起作用，将导致结果树相对较短。只有当两棵树在联合之前等高（通过启发式比较他们的秩值 - 注意我们并不是比较他们实际的 - 当前的 - 高度），那么结果树的秩将增加一个单位。

7-1. 间接路径压缩

还要注意的是，UnionSet函数中调用了FindSet函数，所以路径压缩也被间接使用。每次路径压缩压缩路径时，至少有一个等级值是不正确的。我们不需要去修正这些等级值，因为它们只是作为UnionSet函数的指导性启发。

7-2. 实践案例

在同样的默认示例中，尝试 UnionSet(9, 12)。由于代表不相交集合 {6, 9} 的树当前较高（根据 rank[6] = 1 的值），因此代表不相交集合 {12} 的较矮的树将被插入到顶点6下，而不会增加合并树的高度。

在同样的默认示例中，尝试 UnionSet(0, 11)。注意，顶点3和顶点5的等级是相同的 rank[3] = rank[5] = 2。因此，我们可以将顶点3放在顶点5下（我们的实现），或者将顶点5放在顶点3下（两者都会使合并树的高度增加1）。注意间接的路径压缩启发式在起作用。

7-3. 小测验

Quiz: Starting with N=8 disjoint sets, how tall (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?

Quiz: Starting with N=8 disjoint sets, how short (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?

讨论：为什么？

7-4. 答案

[This is a hidden slide]

8. 实际时间复杂度

到目前为止，我们说FindSet(i)，IsSameSet(i, j)和UnionSet(i, j)的运行时间为O(1)。实际上，如果UFDS同时实现了路径压缩和按秩合并启发式，它们的运行时间为O(α(N))。这个分析相当复杂，在这个可视化中被跳过。

这个α(N)被称为阿克曼函数的逆函数，它的增长速度极慢。对于这个UFDS数据结构的实际使用（假设N ≤ 1M），我们有α(1M) ≈ 1。

9. 附加功能

您已经完成了这个并查集数据结构的基本内容，我们鼓励您进入探索模式，用您自己的例子探索这个简单而有趣的数据结构。

然而，我们还有一些更有趣的并查集挑战给你。

9-1. 源代码

请看以下C++/Python/Java/OCaml实现的面向对象编程（OOP）方式并查集实现：unionfind_ds.cpp | py | java | ml

你可以根据自己的需要自由地定制这个实现，因为一些较难的问题需要对这个基本实现进行定制。

我确实希望有一天C++/Python/Java/OCaml/其他编程语言能将这种有趣的数据结构纳入他们的基础库。

9-2. 在线测验

关于这个数据结构的一些更有趣的问题，请在并查集训练模块上练习。

9-3. 在线评判练习

即使在通过了这个UFDS模块的在线测验后，你认为你已经真正掌握了这种数据结构吗？

让我们来挑战一下你，让你解决两个需要使用并查集的编程问题：UVa 01329 - Corporative Network 和Kattis - Control。

请注意，这两个问题都是实际的国际大学生程序设计竞赛（ICPC）问题，也就是说，它们是 "不简单的"。

9-4. 提示

[This is a hidden slide]

9-5. 合并，查找，拆分？

请注意，并查集数据结构没有 "撤销 "操作。一旦两个不相交的集被合并起来，就不容易再把它们分割成原来的两个集，特别是当路径压缩使合并后的树变平时。

讨论：那么，如果我们需要这种 "拆分 "或 "分割 "或 "切割 "的操作，该怎么做呢？

9-6. 答案

[This is a hidden slide]