小编Dam*_* Hu的帖子

MAKE-SET(x?
    x.p = x
    x.rank = 0

UNION(x, y)
     LINK(FIND-SET(x),FIND-SET(y))

LINK(x, y)
    if x.rank > y.rank
        y.p = x
    else 
        x.p = y
        if x.rand == y.rank
            y.rank = y.rank +1

The FIND-SET procedure with path compression is quite simple:
FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

您可以在《算法导论》第 3章第 21 章中找到伪代码。

这是具有秩和路径压缩的不相交集森林的伪代码。从伪代码中我们可以看出，每次union操作之前，我们都会先找到每个节点的集合号。在路径压缩的 FIND-SET 操作中，x 和 y 的高度将始终只有 2。因为在 FIND-SET 之后 xp 和 yp 都将指向集合的根。为什么仍然需要按等级联合？

Shihab Shahriar 解决了我的问题，他的回答令人印象深刻！