问题标签 [disjoint-sets]

我已经为不相交集编写了这段代码

请注意，在 Find 方法中，我使用了路径压缩，但我没有在任何地方使用按等级联合。这里的时间复杂度会等于树的深度吗？

算法：

图：

(1)--------(2)

邻接列表：

[1] -> [2]

[2] -> [1]

不相交集：

{{1}、{2}}

迭代 1：

边 e = (1, 2)

联合(1, 2)

不相交集 = {{1, 2}}

迭代 2：

边 e = (2, 1)

2 和 1 都属于同一个集合，因此算法检测到一个循环。很明显，该图不包含循环。

该算法完美地适用于有向图。请帮我分析一下。

我原以为会包含这样一个有用的数据结构，C++ Standard Library但我似乎找不到它。

我构建了一个与 Kruskal 的 MST 算法一起使用的不相交集数据结构。我需要加载并合并一个具有 200k 个互连节点的图，我认为我的数据结构实现是一个瓶颈。

您对如何提高性能有什么建议吗？我认为我的 find 方法可能有问题。

编辑：

在阅读了评论并进行了额外的研究后，我意识到我的原始算法设计得多么糟糕。我从头开始，把它放在一起。我将所有分区放入一个哈希表中，并在 find() 中使用了路径压缩。这看起来如何？我应该解决什么明显的问题？

我需要通过属性将数据框随机分成两个不相交的集合'ids'。例如，考虑以下数据框：

我需要获得两个（以一些分数大小随机分隔）数据帧，其中没有相交的ids.

我知道如何以“非熊猫”的方式解决它：

• 获取唯一值ids
• 将唯一值随机分成两个不相交的组
• 根据ids两组中的值选择行.isin()

我想知道是否有一种简单而简洁的方法可以使用一些 pandas 内置函数来完成，比如.sample()？

我有一个关于不相交匹配模式的问题。当每个案例没有踩到其他案例时，匹配模式是不相交的。

我的问题：“if”语句是否也算在内，以检查这些情况是否不相交？因此，如果我们有这样的修补模式，则意味着最后一种情况也包括第二种情况，并且无论如何它都不会脱节。但是如果我将最后一个案例更改为

匹配模式会被认为是不相交的吗？

给定一个由“1”（云）和“0”（晴空）组成的 2D 网格天空图，计算云的数量。

云被晴朗的天空包围，由相邻的云水平或垂直连接而成。您可以假设天空图的所有四个边缘都被晴朗的天空包围。

例子

输出应该是

为了

输出应该是

我正在为我的有向图寻找一个有效的联合查找（又名不相交集）数据结构，它有循环和森林。鉴于这样的图表，我想回答以下问题：G

1. 我可以v从到达节点u吗？
2. u从哪些节点无法访问？

对于单个“源”节点u，我可以运行DFS搜索并回答是否可以从中访问v。m + n在最坏情况下，单个 DFS 搜索的上限成本为，其中m和n分别是图中的顶点数和边数。但是，我有很多这样的“源”节点，我想知道是否有比与所有“源”节点分开运行 DFS 更好的方法（在最坏的情况下m，它的上限成本为。）m * (m + n)

似乎这两个问题都可以通过有向图的 Union-Find 数据结构来有效地回答。令我惊讶的是，经过大量在线搜索后，我找不到任何解决方案。我是否在错误的方向思考问题？

我找到了这个答案，但无法理解。

有没有比计算它们的交集更容易/更快的方法来确定两个字典是否不相交？

对于交集，我找到了这个答案，所以不相交测试看起来像这样：

但是我认为这是低效的，因为它总是计算整个交叉点（没有短路退出）。

有更好的想法吗？

我找到了一个创建制作和查找方法的教程

这里是完整代码的链接 这里是Kruskal 算法的链接

我很困惑为什么他们要返回一个其父节点本身而不是不同节点的节点，以及在等级设置为 0 时实施联合时等级的用途。我尝试查找其他 Kruskal 算法代码和解释，但是很少有关于实施的资料。