最终改进联合的排名与越界存储

在与路径压缩相结合的情况下，按行进行联合几乎实现了对联合查找数据结构的恒定时间操作，最后一个技巧允许我们通过将秩存储在超出范围的条目中来完全摆脱 rank 存储。parentarray。它基于以下观察：

• 我们实际上只需要存储代表的等级，而不是其他元素。对于这些代表，我们不需要存储 parent。
• 到目前为止，parent[i] 最多只是 size - 1，即较大的值未被使用。
• 所有级别最多 。

这带来了以下方法：

• 而不是条件 parent[i] == i，我们现在通过
  parent[i] >= size 确定代表
• 我们使用这些越界值来存储集合的等级，即具有代表性的集合 ihas rank parent[i] - size
• 因此，我们使用 parent[i] = size 而不是 parent[i] = i 初始化父数组，即每个集合是其自己的代表，其等级为 0。

由于我们只通过 size 来抵消等级值，我们可以在 merge 的实现中简单地用 parent 向量替换 rank 向量，只需要在 find 中交换条件识别代码：

通过排名和路径压缩使用 union 完成的实现：

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (parent[pi] < parent[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (parent[pi] > parent[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++parent[pi];
        }
    }
};