问题标签 [disjoint-union]

我正在编写代码以在图表上执行联合查找，

输入的第一行是：
nm [n是节点数，m是边数]

然后是m行，表示连接了哪两个节点

当我遇到每条边时，我会执行联合操作来连接节点。执行并集后，我还想知道最大子集和最小子集的大小

到目前为止，这是我的代码，

我正在使用蛮力来获得最小尺寸的子集和最大尺寸的子集。此代码在 Sphere Online Judge 中超时。

获得最小尺寸子集和最大尺寸子集的更有效方法是什么。

SPOJ 问题链接是：http ://www.spoj.com/problems/LOSTNSURVIVED/

我目前正在比较Google Closure Compiler和Flow静态类型检查器的表现力。我喜欢后者的是它显然可以很好地代表标记的联合。手册给出了这个例子：

有没有办法使用 Closure Compiler 来做这样的事情？这意味着某种方式可以强制对象的某些属性不仅是特定类型，而且具有固定值？并使用该值进行类型推断，以区分联合中的不同选项？我没有找到有关此效果的文档。

为了突出显示单个字符串中的多个搜索文本元素，我有一个例程计算要在字符串本身中突出显示的范围。

例如，如果我his+is在字符串“这是我的错误测试”中搜索字符串，我会得到高亮显示的范围[1,3]、[2,3]、[5,6]和[12,13]。

所以我想要的结果是[1,3],[5,6]和[12,13]。

有没有从上面的列表中提取非重叠范围的一般方法？或者事件更好，是否有特定于字符串的方法来获取这些？

算法：

图：

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

邻接列表：

[1] -> [2]

[2] -> [1]

不相交集：

{{1}、{2}}

迭代 1：

边 e = (1, 2)

联合(1, 2)

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

迭代 2：

边 e = (2, 1)

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

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

假设我有一个元素对列表，例如 (1, 2) (3, 4)，其中不存在重复项，并且对于一对 (p, q) p != q。如何使用简单的代码从这些元素中形成一个集合（我不打算使用像不相交集合和联合这样的数据结构，而是使用 java 库 API——除非代码可以以简单的方式编写）。示例： (1, 2) (2, 4) (5, 6) (4, 7) (3, 5) 应该输出： {1, 2, 4, 7} 和 {3, 5, 6}

这是一种不正确的幼稚方法。如果我得到一个序列 (1 2) (3 4) 和 (2 3)，则输出变为 {1, 2, 3} 和 {3, 4}。

发生这种情况是因为集合列表是这样创建的：{1, 2} 然后 {3, 4} 然后当对 (2 3) 出现时，它不会合并 2 个集合。

我可以编写一个代码来检查第一个值是否存在于任何集合中，比如 S1，然后对于另一个值相同，比如 S2，然后合并：

太多的循环和条件。有更简单的解决方案吗？

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

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

例子

输出应该是

为了

输出应该是

网上有很多关于不相交集结构的描述和例子。

在某些情况下，对于每个集合，它都存储“排名”。当一个集合合并到另一个集合中时，如果它们的等级相同，则前者的等级增加 1。

在其他情况下，对于每个集合，它都会存储其大小。当一个集合合并到另一个集合中时，它们的大小会被添加。

在这里它存储排名。

在维基百科文章中，它存储排名。

在康奈尔大学的讲义中，它存储了排名。

在Sedgewick 和 Wayne的“算法”示例中，它存储大小。

在这里，它还存储尺寸（主站点）。

科门等人。写：

显而易见的方法是使具有较少节点的树的根指向具有更多节点的树的根。我们将使用一种简化分析的方法，而不是显式地跟踪以每个节点为根的子树的大小。对于每个节点，我们维护一个等级，它是节点高度的上限。在按秩联合中，我们在 UNION 操作期间使秩较小的根指向秩较大的根。

哪个更好/更合适？

我有包含重复值的单元格，我想快速合并它们。该表如下所示：

重复的单元格范围可能是不相交的或不相邻的单元格。我想要一种方法来快速识别此类重复范围并在不使用 For 循环的情况下合并它们。[不知道，但认为可能有一种最快的创新方法，无需循环，可能使用 Excel 数组公式和 VBA 代码的某种组合来选择和合并重复的单元格区域。]

顺便说一句，上面的代码可以正常工作，直到它在.Merge行出现以下错误。

编辑这是显示arr内容以及R.Address 的 Watch 窗口的快照。

输出： 不需要任何选择，这只是为了演示目的：

输出应如下所示：

编辑... 假设行中的重复值相同？所以只有重复的列值被合并。必须有一种快速、创新的方式来进行这种合并。

最终输出图像：

我们应该使用哪种方法来查找所有断开连接的图，为什么？

由于BFS和DFS遍历都是遍历方法，并且是多次遍历。我们可以找到所有断开连接的组件。
另一种方法可以是kruskal (MST) 中使用的不相交集来查找不连接的组件。

由于很长时间以来我一直在尝试从测验中解决一个问题，但我得到了错误的答案，问题如下：-

假设不相交集数据结构被实现为不相交树，并按秩启发式联合。

执行代码后计算结果树的高度的乘积。例如，对于由高度为 1、2、3、1 的四棵树组成的森林，答案将是 6。（回想一下，树的高度是从根到叶的最长路径上的边数。在特别是，仅由一个节点组成的树的高度等于 0。）

我解决了这个问题并得到答案为5（2 * 2 * 1），但我提交时显示错误，我尝试了很多次，请我计算这个......