给定并查集操作序列，如何计算最终森林中树的最大高度？

让我们一步步拆解这个问题，搞清楚最终森林里树的最大高度是多少：

首先，先明确两个核心启发式的作用：

• 按秩合并：在Union操作时，我们会把秩（树高度的上界）较小的树合并到秩较大的树的根节点下，只有当两个树秩相同时，合并后根的秩才会加1。这个操作是为了避免树退化成链表，尽量保持树的高度更小。
• 路径压缩：只在Find操作时触发，它会把当前节点到根节点路径上的所有节点直接连接到根节点。这一步会彻底扁平化树的结构，让后续操作效率更高。

接下来看完整操作流程：

1. 初始化MakeSet：1到60每个元素都是独立的树，每个节点自身是根，初始秩为0（对应高度1，因为单个节点的树边数为0）。
2. 三轮Union操作：
   • 第一轮Union(i,2i)：把每个数和它的2倍合并，形成一批以奇数为起点、包含其2的幂次倍数的集合。
   • 第二轮Union(i,3i)：把每个数和它的3倍合并，这会把之前的集合和3的倍数集合进一步合并，比如1的集合会合并3、9、27等。
   • 第三轮Union(i,5i)：把每个数和它的5倍合并，继续扩大集合范围，比如1的集合会合并5、10、20等。
     这三轮Union操作后，树会有一定高度，但因为按秩合并的约束，高度被控制在较小范围。
3. 全量Find操作：对1到60的每个元素执行Find(i)。这一步是关键：每个Find操作都会把当前节点到根的路径上所有节点直接连到根节点。比如原本有一条路径7->14->28->56，执行Find(56)后，14、28、56都会直接成为7的子节点，这条路径被彻底扁平化。

当所有Find操作完成后，每个集合里的所有非根节点的父节点都是根节点，也就是说，每棵树的结构都是根节点直接连接所有其他节点，树的实际高度为1（按边数定义的高度）。

所以最终森林中树的最大高度是1。

内容的提问来源于stack exchange，提问作者fds