最終改進聯合的排名與越界儲存

在與路徑壓縮相結合的情況下，按行進行聯合幾乎實現了對聯合查詢資料結構的恆定時間操作，最後一個技巧允許我們通過將秩儲存在超出範圍的條目中來完全擺脫 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];
        }
    }
};