并查集 (Union-Find Disjoint Sets, 简称UFDS)
1. Introduction
并查集（UFDS）数据结构被用来模拟多个不相交集，它能够有效率地（即在几乎常数的时间内）确定一个元素属于哪个集，测试两个元素是否属于同一个集，并在需要时将两个不相交集合并为一个。它可以用来寻找无向图中的连接分量，因此可以作为最小生成树（MST）问题的Kruskal算法的一部分。
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]