如何计算结果林中一棵树的最大高度？

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)

假设不相交集数据结构被实现为具有按等级启发式联合和路径压缩启发式的不相交树。

计算结果林中一棵树的最大高度。

Answer 1

答案为1

这里是解释：

森林中至少有一棵高1的树。此外，自从最后一个for循环调用所有60个元素的Find（）以来，所有树的高度最多为1。由于使用了路径压缩，因此在此循环中，每个非根节点都将直接连接到相应的根，因此所有树的高度最多为1。