计算不交集的高度

Question

考虑程序

for i from 1 to 60:
  MakeSet(i)
for i from 1 to 30:
  Union(i, 2*i)
for i from 1 to 20:
  Union(i, 3*i)
for i from 1 to 12:
  Union(i, 5*i)
for i from 1 to 60:
  Find(i)

我想确定不交集的高度。

我了解什么？

MakeSet（i）创建一个新集合，其唯一成员由i指向，并且

Unique（i，j）将包含对象i和j的两个动态集组合为一个新集Si ∪ Sj

因此，第一个for循环将填充一个包含60个元素的集合，然后第二个for循环将这些元素组合在一起，使该集合的60的十分之一为30，但是接下来我们使用3 * i，而i范围直到20，所以它不会超出范围。还是我理解错了？

不交集的高度是多少？

提前感谢。

Answer 1

我不知道您所说的高度是什么意思，但是在这里，Union（i，j）表示包含元素i的集合和包含元素j的集合将被合并。尽管如此，合并后的集合仍包含先前属于包含i和j的集合的所有元素。

for i from 1 to 20:
  Union(i, 3*i)

上面的代码表示包含元素i的集合将与包含元素3 * i的集合合并。因此，它不会超出范围。

最后，Find（i）会告诉哪个集合包含元素i。