2

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

Consider the program:

for i from 1 to 12:
MakeSet(i)
Union(2, 10)
Union(7, 5)
Union(6, 1)
Union(3, 4)
Union(5, 11)
Union(7, 8)
Union(7, 3)
Union(12, 2)
Union(9, 6)

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

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

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

4

1 回答 1

1

我想到了！答案是2。用正确的解释：对！将有 3 棵高度为 1、1 和 2 的树。（我在 edx 上遇到了这个问题，但该提交只需要 2 作为答案）

我猜这棵树应该是这样的：

    tree1,tree2,tree 3

0 级：4、1、2

一级：3 5 , 6 9 , 10 12

2级：8 7 11

你可以试试这个可视化网站https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html

于 2019-03-05T12:07:59.107 回答