问题标签 [union-find]

这是参考 Robert Sedgewick 和 kevin Wayne 所著的《算法（第四版）》一书

对于 Union-find 实现，find 和 union 的代码如下（第 222 页）给出：

然后是一个命题：

命题 F。快速查找算法对 find() 的每次调用使用一次数组访问，对结合两个组件的 union() 的每次调用使用 N + 3 到 2N + 1 次数组访问。

我想了解我们实际上是如何到达N + 3和2N + 1的。我对 N + 3 有一些想法，但对 2N + 1 不知道。请帮忙。

我正在解决这个挑战：https ://open.kattis.com/problems/virtualfriends

我的解决方案似乎有效，但 kattis 的测试用例运行速度太慢，所以我想知道如何提高代码效率。我正在使用定制的联合查找结构来执行此操作，将“朋友”存储到树形图中以供参考。

这是Narasimha Karumanchi 的数据结构书的一段（不相交集ADT ）

快速查找实现（快速查找）

此方法使用一个数组，其中数组包含每个元素的集合名称。

在这个表示中执行 union(a,b)[假设 a, 在集合 i 中，b 在集合 j 中] 我们需要扫描整个数组并将所有 i 更改为 j。这需要 O(n)。

我的问题 1

如果查找操作需要 O(1) 那么为什么要扫描完整的数组并将所有 i 更改为 j ，其中只有两个需要更改，所以它是 O(n)

=============

（书 8.8 节）

我的 2. 问题

它如何使用父母解决问题？以及根方法和父方法如何为我们提供倾斜树？

我发现一些在线union-find 教程描述了路径压缩技术，甚至比O(log(N))复杂性还要低find()，下面是这个博客中的路径压缩实现，

我看到这个实现只是将路径减少了一半，并且可以使用下面的递归技巧来进一步压缩，

我想知道我是否遗漏了什么，为什么大多数在线教程都没有讨论这种技术？

问题本质上是我发现 union-find 方法的递归版本比迭代版本快。

问题的背景在这里：好或坏的平衡。

问题说我们有一个平衡，但我们不知道它是好是坏。我们有两种重量不同的物品，同一种物品重量相同。我们将所有项目索引到 1,2,3..n。我们随机挑选其中两个并称重。每个称重结果以 x,u,v 的形式表示，其中 x 是位指示符，0 表示平衡，1 表示不平衡，而 u 和 v 是两个项目的索引。

如果天平不好，就会出现矛盾，比如我们有这样的称量结果：

item 1 和 item 2 在两个措施中的关系不同，所以平衡不好。我需要编写一个程序来告诉最早可以确定余额是坏还是好的度量。

基本上，这是经典并集问题的变体。我希望迭代联合查找方法可以带来更好的性能，但是当递归版本被接受时，我得到了 Time Limit Exceeded。我想问这是为什么？？？

这是我算法的完整版本。

一个示例测试用例是

我正在尝试创建一些Strings 集，然后合并其中一些集，以便它们具有相同的标签（类型usize）。初始化地图后，我开始添加字符串：

当我调用self.clusters.find("a")andself.clusters.find("b")时，会返回不同的值，这很好，因为我还没有合并集合。然后我调用下面的方法来合并两组

如果我现在打电话self.clusters.find("a")，self.clusters.find("b")我会得到相同的价值。但是，当我调用该finalize()方法并尝试遍历地图时，会返回原始标签，就好像我从未合并集合一样。

我不知道为什么会这样，但我对 Rust 比较陌生；也许是指针的问题？

我实际上使用的不是“a”和“b”，而是utils::arr_to_hex(&input.outpoint.txid)type String。

这是我正在使用的 Union-Find 算法的 Rust 实现：

基本上是在寻找支持这种数据结构OOTB的数据库

我正在学习联合查找。

我了解这些联合操作如何组合在一起制作此图，但我不了解 ID 变量是如何分配的。起初，我认为这是每个图的大小，但事实并非如此，因为第一个图的大小是 5，第二个图的大小是 3。任何帮助将不胜感激。

这是问题的链接：

我已经使用联合查找算法来解决这个问题。代码：

我的程序中使用的逻辑：要找到答案，取一个连通分量中所有有效值的最小值。现在要使图形连通，取我们从上述步骤得到的所有值的最小值，并从该节点到所有剩余节点。如果图已经连接，则答案为 0。如果存在一个连接组件，其中所有节点均无效，则无法选择答案 (-1)。

但是这个解决方案不被接受？它有什么问题？

任务是找出“find”和“union”的Union-Find结构中m个操作的最坏情况下的时间复杂度，此时所有“union”操作都发生在所有“find”操作之前。

union-find 结构从 n 个不相交的集合开始，每个集合包含一个元素。此外，每个集合都表示为一棵树，该结构使用路径压缩和按秩联合。

我的想法是，首先，所有联合操作一起将花费 O(log(n))，因为每个都花费 O(1)，并且可能发生的操作不超过 log(n)。

之后，如果我们查看查找元素，那么对于每个元素，第一次查找将花费 O(log(n))，但下一次查找其路径中的每个元素将花费 O(1)。因此它将花费更少的时间 O(m*log(n))。

我不确定如何从这里继续。我认为这可能需要：

log(n) + log(n/2) + log(n/4) + .... = log(n)*log(n)

因为每次我们需要上去的路径级别都会变短。

然而。我不确定，也看不到此处使用了 m 参数。也许还需要在分析中使用逆阿克曼函数，但我不知道如何。