问题标签 [disjoint-sets]

假设 unordered listA = [1 2 3]st all elements distinct
和 unordered listB = [1 2 3 4 5]st all elements distinct

最初的问题是：
我如何选择len(listA)时间，listB 的元素不在
listA 中
并且彼此不同。

更新为：
我如何选择len(listB)-len(listA)时间，listB 的元素不在
listA 中
并且彼此不同。

对于更新后的案例，Pynchia 给出的答案变为：
newList = list(set(bRightbLeft) - set(aLeft))[:len(bRightbLeft)-len(aLeft))]

如何以最佳方式通过桥（链接）连接两个图？

有一些标准，例如每个链接的权重、链接的稳定性（连接质量）、预期的连接时间等。我想知道如何根据它们定义成本函数？换句话说，我如何量化上述标准？

任何文章或讲义都会有很大帮助。

我正在尝试使用 DisjSet 算法构建迷宫。我觉得我已经搞定了，但由于某种原因，我无法弄清楚为什么我在我正在使用的一个类中不断收到这个空指针异常。任何帮助将不胜感激

这是迷宫课

这是 DisjSet 类

这是排列类

错误是

而这一切又都指向了排列类中的这行代码

先感谢您

我在 CodeChef 上解决了这个问题并浏览了社论。

这是实现的不相交集算法的伪代码：

union和的时间复杂度是find多少？

IMO，时间复杂度find是O(depth)，所以在最坏的情况下，如果我不使用路径压缩，复杂度结果是 O(n)。由于union也使用find，因此它也具有 O(n) 的复杂度。相反，如果我们丢弃findfromunion并将两个集合的父级传递给union，则复杂度union为 O(1)。请纠正我，如果我错了。

如果应用路径压缩，那么时间复杂度是多少？

这是问题的链接：prob https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2737

以下是我的实现。我尝试了他们的示例测试用例和其他多个测试用例，他们都给出了正确的答案。但是当我提交时，我不断收到错误的答案。在此之前，我用向量向量实现了这个，我得到了“超出时间限制”。我不确定代码有什么问题，如果有人可以帮助确定我的解决方案失败的测试用例，我将不胜感激。

首先，我主要用 python 做了一些非常琐碎的事情，所以我对 pythonic 语法不是很满意。我正在学习不相交集，并对实现有基本的了解。

我遇到了一个 python 森林实现（不是我的！），并且很难理解字典的__init__工作原理。wikipedia 的例子很容易理解（这个实现是基于wiki 的伪代码）。特别是，这条线对我来说很陌生

我看不到这个 dict 构造函数在做什么，我的猜测是对于从0to的每个数字vertices， av都作为键和值插入到字典中，但是键有一个包含v和附加的子集0？我可能大错特错。

另外，当我比较python代码时

维基百科的伪代码，

我试图了解[0]'s 和[1]'s 是如何使用的。我只能通过[0]我们如何初始化字典结构来建立联系。当然，仅基于比较，就很容易知道它们指的是什么，但是在结构中使用 0 和 1 是如何做到的呢？

此外，如果您需要我正在谈论的整个代码，您可以在此处找到它。

我有一些关于不相交集的代码。

我想添加查找、合并和初始化功能。在代码的顶部，它告诉每个函数必须做什么。我已经找到并合并了，我希望他们是对的。但是我无法获得初始化功能。我不知道如何让它返回一个新的集合系统，每个集合一个元素。你们能帮我吗？

下面是我的查找和合并功能：

如果我有 n 个单节点树和 m 个查找集合操作（​​注意：没有联合，假设之前已经完成了联合）并且只使用路径压缩，这真的需要 O(m) 时间吗？我一直试图证明这一点，但似乎并非如此。由于联合没有按等级使用联合，因此查找集可能需要 O(n) 时间。但是仍然有可能在 O(m) 时间内完成 m 查找集吗？

我正在尝试使用预制的不相交集类创建迷宫。我创建了一个 Cell 类，其中包含四个墙壁中的每一个的布尔变量。问题是，如何创建一组不相交的单元格对象？这样我就可以合并单元格并相应地更改布尔变量。

http://users.cis.fiu.edu/~weiss/dsaajava3/code/DisjSets.java

那是不相交集的代码

我们用树实现了不相交的数据结构。在这个数据结构中，makeset()创建一个包含一个元素的集合，merge(i, j)合并两个集合树，i这样j高度较低的树成为第二棵树的根的子节点。如果我们以随机方式进行n makeset()操作和n-1 merge()操作，然后进行一次查找操作。在最坏的情况下，这种查找操作的成本是多少？

答案：四。

任何人都可以提到作者获得此解决方案的好技巧吗？