问题标签 [union-find]

我正在尝试使用 kruskal 算法在 spoj 上解决这个 MST 问题。我的程序似乎适用于所有测试用例，但 spoj 反复在此代码上提供 WA。

我无法在此代码上找到任何失败的测试用例。有人可以指出我做错了什么。

请注意，这不是家庭作业问题。我正在对 Kattis 进行培训，我遇到了一个需要使用 Union-Find 范式的问题。鉴于问题的性质，我决定实现自己的 UnionFind 数据结构。我了解我的 DS 接口应支持：

1. 制作集
2. find(elem) -> 返回对该集合代表的引用
3. merge(firstElem, secondElem) -> 合并该集合的两个父节点（同时确保它是平衡的）

现在的问题是我没有实现这个数据结构来支持整数，它通常使用一个数组来实现，其中索引是值，集合的代表总是该索引处的值。相反，我的集合包含字符串，我发现选择数据结构有困难。

我正在研究关于不相交集的算法。

和章节Fast FIND Implementation (Quick Find)

数据结构如下图所示：

例如）

在[number] = set name（上面的示例）中，数字是集合名称中的元素。

所以，数字 0 在第 3 组中，第 1 号在第 5 组中，等等。

要进行 Union(a, b) （假设 a 在集合 i 中，b 在集合 j 中），它需要 O(n) 操作。我知道这个。原因如下图（伪代码）：

但是，在书中，我无法理解：

在最坏的情况下，一系列 n - 1 个联合需要 O(n^2) 时间。如果有 O(n^2) 次 FIND 操作，则此性能很好，因为每个 UNION 或 FIND 操作的平均时间复杂度为 O(1)。如果 FIND 较少，则这种复杂性是不可接受的。

我不明白这些句子的含义是什么，为什么复杂度是 O(n^2)。无法想象我上面写的代码这样的复杂性。

在 coursera 课程中，以下联合查找仅适用于数字： https ://www.coursera.org/learn/introduction-to-algorithms/lecture/EcF3P/quick-find

在幻灯片的最后，如何计算每秒 10^9 次操作和其他 10^x 个数字（包括 10 个）？所有数字都在下图中：（文字也在下面复制）

粗略的标准（目前）。

• 每秒 10^9 次操作。
• 10^9 字的主存。
• 在大约 1 秒内触摸所有单词。

前任。快速查找的巨大问题。

• 10^9 个对象上的 10^9 个联合命令。
• 快速查找需要超过 10^18 次操作。
• 30 多年的计算机时间！

我一直在阅读有关联合查找问题的信息。两个主要改进是路径压缩和按等级联合。据我了解，按等级联合用于确定如何组合不相交的树。如果我们有两棵不相交的树 T1 和 T2，那么我们将具有较小等级的树的根附加到具有较高等级的树上。如果我们不使用路径压缩，那么排名只是树的深度。这是有道理的，因为我们不想增加输出树的深度，因为它直接影响查找和联合。

我的问题是当我们也使用路径压缩时。我一直在读到这两种优化相辅相成，但我没有看到。由于路径压缩，排名不再是树的深度（它成为深度的上限）。假设 T1 有 2 个分支（设 T1 的 rank 为 3），T2 的深度为 2，rank 为 2。现在假设我们在下面标有“*”的 T1 的叶子上执行查找操作（带有路径压缩）。现在，如果我们联合 T1 的根和 T2 的根，那么 T2 将附加到 T1 的根（因为查找不会更新排名）。结果树的深度为 3。但如果我们将 T1 附加到 T2，我们可能会有更好的性能。

在 T1("*") 的叶子上找到后，然后在 T1 和 T2 的根上并集，我们得到

我在这里错过了什么吗？路径压缩和按等级联合如何相互补充？我知道等级只是树深度的上限，但我看不出按等级联合如何提高结构的整体性能。这比随机组合根的联合更好吗？

我在这里先向您的帮助表示感谢。

当我们合并两个集合时，例如 A={1,2,3} 和 B={6,7,8}，让 1,8 分别代表这两个集合，现在如果我们合并两个集合会是什么结果集的代表？我们可以根据我们的选择来选择吗？在我下面的代码中

我得到的答案是 1？如果我们希望它更改为另一个代表怎么办？

在尝试使用 Java 进行快速查找时，我遇到了问题。在 main 函数中，while 循环之后的代码没有被执行，即使它看起来不像是无限循环的情况。添加完整的代码和示例输入和输出。

更新：- hasNext() 的阻塞性问题，hasNext() 一直在等待输入。在给出所有输入后使用Ctrl+Zwhile来终止流，这有助于在循环后处理剩余的代码

以下是完整代码（有问题） -

样本输入 ->

对应输出->

我阅读了 wiki 页面，但不明白为什么将较小的列表附加到较大的列表中很重要。

这是 wiki 页面中算法的一部分：

假设您有一个列表集合，并且每个列表的每个节点都包含一个对象、它所属的列表的名称以及该列表中的元素数。还假设所有列表中的元素总数为 n（即总共有 n 个元素）。我们希望能够合并这些列表中的任何两个，并更新它们的所有节点，以便它们仍然包含它们所属的列表的名称。合并列表 A 和 B 的规则是，如果 A 大于 B，则将 B 的元素合并到 A 中并更新曾经属于 B 的元素，反之亦然。

如何计算快速联合算法的最坏情况。实际上，当涉及到树的高度时，我总是在时间复杂度上苦苦挣扎。我知道它与 O(h) 有关，但是树是在代码中开发的。

那么正确的方法应该是什么？

我在执行一个实现快速联合算法的简单程序时遇到了这个错误。我找不到花括号有什么问题。我已经发布了下面的代码。请审查它。