问题标签 [disjoint-sets]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
0 回答
315 浏览

c++ - 带链表的不相交集,C++ - Cormen

这是我根据 Cormen 实现的不相交集(算法简介 - 第 2 版第 21 章)。
删除对象(“~DisjointSet”析构函数)时出现问题。
这是因为“std::vector sets;”的寄存器。可能指向相同的“MetaSet*”。

0 投票
0 回答
33 浏览

boost - boost - 从不相交的集合中获取组件多图

我是 boost 库的新手。我在图上创建了一个不相交的集合结构,上面有一些分区,获得集合组件的多重图的最佳方法是什么?

0 投票
1 回答
83 浏览

algorithm - 在简化图中逐步查找不相交集的数量

我在图中找到不相交集的数量,G然后删除图的一些顶点G并制作图G',我想在其中找到不相交集的数量G',是否有任何好的算法不做与G'我们一样的事情到G

0 投票
4 回答
1953 浏览

algorithm - 确定两组数字是否不相交的有效算法

练习软件开发人员面试并被困在算法问题上。

0 投票
2 回答
718 浏览

algorithm - 有没有一个例子可以在Omega(q log n)中运行Union&find算法而无需按等级运行?

最近,我读到这篇文章,惊讶地发现,仅使用路径压缩的 union & find 算法的时间复杂度是O((m+n) log n),其中m'find' 查询n的数量是 'merge' 查询的数量。

我对这种复杂性很感兴趣,(因为我通常在没有秩的情况下实现这个算法,即使我按秩倒置应用联合,性能也不错!)并试图找到一个可以使时间复杂度提高的例子。但是因为路径压缩的威力很大,所以真的很难……

有没有可以实现的例子Omega((m+n) log n),或者这种复杂性只是理论上的,而不是实际的?

0 投票
1 回答
741 浏览

c++ - 如何从“不相交集”中获取所有元素的列表

在我的问题中,我有一堆元素(类元素)。假设我有 1000 个元素。这些元素最初是不相关的,这意味着它们在自己的集合中。

稍后我需要根据我的程序流程使用联合操作来合并其中的一些集合。我计划使用 boost 库的 disjoint_set ( http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html )

我的问题是如何在给定集合代表的情况下列出集合中的元素。

disjoint_set 是此类任务的最佳数据结构吗?那么我应该考虑使用其他东西吗?

0 投票
1 回答
1203 浏览

c++ - 提升不相交集

我需要制作一个不相交的类型集dataum

我在向量中的所有数据如下

然后我创建 disjoint_set

这似乎不起作用。我错过了什么?我想用自定义数据类型创建一个不相交的集合。在这种情况下dataum。最初,我的每个人dataums都应该在不同的集合中。

0 投票
1 回答
138 浏览

python - 关于在python中实现不相交集数据结构的一些问题

所以我只是使用了这里提供的代码:http: //www.ics.uci.edu/~eppstein/PADS/UnionFind.py,但我遇到了一些关于代码的问题:

首先,方法iter是什么意思或做什么?

其次,假设我最初有以下代码:

那么,我怎样才能执行打印、添加等集合的常规操作呢?如果我写 print R,它只会给出 < main .UnionFind instance at 0x000000000A31F048>,这显然不是我想要的。如果我写 R.add('K') (将新元素 'K' 添加到集合 R),我会得到 'AttributeError: UnionFind instance has no attribute 'add''。这是否意味着我需要为“添加”定义一个属性?这个怎么做?

如果经过几次联合操作后,我将“A”、“B”、“C”分组到同一个集合中,那么如果我想知道“A”所在的集合内的所有元素(即“A”, 'B','C'),我该怎么办?

谢谢

0 投票
1 回答
1159 浏览

python - 在 Python 中实现不相交集数据结构

我正在做一个涉及集群的小项目,我认为这里给出的代码https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py可能是我工作的一个很好的起点。但是,在我的工作中实施它时遇到了一些困难:

  1. 如果我制作一个包含所有集群 cluster=set([0,1,2,3,4,...,99]) 的集合(有 100 个点,数字标记它们),那么我想分组将数字放入簇中,我是否只需编写 cluster=UnionFind()?现在集群的数据类型是什么?

  2. 如何在集群上执行常规操作?例如,我想读取集群中的所有点(可能已组合在一起),但键入 print cluster 会导致 < main .UnionFind instance at 0x00000000082F6408>。我还想不断向集群添加新元素,我该怎么做?UnionFind()的具体方法需要写吗?

  3. 我如何知道一个组的所有成员及其成员之一被调用?比如 0,1,3,4 组合在一起,那么如果我调用 3,我希望它打印 0,1,3,4,我该怎么做呢?

谢谢

0 投票
1 回答
168 浏览

complexity-theory - 证明任何求解不相交集的算法至少需要 nlog n

不相交集问题

让 A 和 B 成为两个集合,它们是不相交的吗?

问题

证明任何求解不相交集的算法至少需要O(nlog n)

我想到的想法是证明排序可以简化为不相交集问题。

我怎么做 ?