问题标签 [disjoint-union]

我想定义一个类 AorB，这样所有 A 都是 AorB，所有 B 都是 AorB，而这些都是 AorB。当然，A 和 B 应该是 AorB 的子类。问题在于AorB.__init__，当我无法说服自己时，它应该是别的东西。我可以定义一个 AorB 工厂，但如果可能的话，我宁愿拥有 AorB 构造函数。

我知道分配给 self 在这里不起作用，但我只是想表明意图。正如我所说， factory (from_par) 工作正常，我只想将其称为AorB，而不是AorB.from_par。

PS。我知道，__init__可能为时已晚，自我的类型已经确定。随意在您的答案中使用元类。是时候让我了解一些关于它们的有用信息了。:-)

我正在实施不相交集数据结构来进行联合查找。我在 Wikipedia 中看到了以下声明：

...每当相同等级 r 的两棵树联合起来时，结果的等级为 r+1。

当树的等级相同时，为什么连接树的等级只增加一？如果我简单地添加两个等级（即2*r）会发生什么？

我一直在研究不相交的集合数据结构。

我有一个查询，在同时使用按等级联合和路径压缩时，如果我们跳过使用按等级联合和分配优先级（父）而没有任何等级比较（根/代表元素的等级）的两组（树）会影响运行时间。

尽管在合并两个集合时需要加权联合启发式，但将较小的集合附加到较大的集合以使更新尽可能少以指向代表元素。

Union-by-rank（类似于weighted-union）在合并两个集合时使用。但是如果我们跳过比较排名并随机分配优先级，它不会影响运行时间？那我们为什么要使用它..看不清楚，如果我错了，请帮助我理解它。

//不进行排名比较

联合（x，y）

x.父=y;

通用代码

我正在尝试生成一个具有可遍历和不可遍历位置的随机网格，并确保在 4 个方向之一{右、上、左、下}中存在从一个可遍历位置到任何其他可遍历位置的路径。可遍历位置表示为“[ ]”，不可遍历位置表示为“[X]”

我可以使用什么算法来查找网格中的不相交集并在不相交集之间创建路径？谢谢！

我说的是union-find-disjoint 数据结构。互联网上有很多关于如何实现这一点的资源。到目前为止，我已经了解了两种联合优化技术。第一个是通过变量 Rank 来“平衡”树，它表示最深节点的深度，因此是 find() 的上限。第二个优化是：设置一个对象的父节点为头节点，同时调用find()（设置中还包含了对象的父节点，所以变成了级联优化）。

但是，当实现同时使用它们两者时，它们通常会不加思索地将两者合并在一起。具体来说，GeeksforGeeks（仅作为示例，没有任何个人内容）这样做。这不会导致排名“损坏”和 O(log n) 复杂性吗？

例如，如果我有一长串节点（5 到 4 到 3 到 2 到 1 到 0，这是头部）并且我调用 find() 到 2，则排名保持 5，即使它应该是 3。

我有两个列表，我想获得两个列表的不相交并集的列表。也就是说，两个列表中都不包含的所有项目。

这篇文章的查询与我的几乎相同，只是它们的含义与 Disjoint Union 略有不同：Disjoint Union in LINQ

这个代码片段有什么问题？

我遇到类型转换问题

对于那些不熟悉不相交集数据结构的人。

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

我正在努力寻找答案。来自给定朋友组的朋友组及其关系。当然，毫无疑问，这可以使用 BFS/DFS 轻松实现。但是我选择使用不相交集，我也倾向于找到该人所属的朋友组等，并且不相交集听起来确实适合这种情况。

我已经实现了不相交集数据结构，现在我需要找到它包含的不相交集的数量（这会给我组数）。

现在，我坚持如何有效地找到不相交集的数量，因为朋友的数量可以大到 1 00 00 0。

我认为应该有效的选项。

1. 将新套装附在原件背面，并销毁旧套装。

2. 在每个工会中更改每个元素的父级。

但是由于朋友的数量很大，我不确定这是否是正确的方法，也许是否有任何其他有效的方法或者我应该继续实施上述任何方法。

这是我的代码以获取更多详细信息。（我没有在这里实现计数不相交集）

下面是我跟踪不相交集森林中每棵树的大小的实现。

你能告诉我它有什么问题吗？我正在尝试解决 UVa 问题https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3638

上面代码中的链接函数完成了更新树大小的工作。

解决问题的方法是找到元素0所属的集合，得到该集合的代表元素的大小。但是我得到了这个代码的错误答案。

你能帮我么

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

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