根據規模改進聯合

在我們當前的 merge 實現中，我們總是選擇左側集合作為正確集合的子集，而不考慮集合的大小。沒有這個限制，從元素到其代表的路徑（沒有路徑壓縮 ）可能很長，從而導致 find 呼叫的大執行時間。

另一個常見的改進是通過大小啟發式聯合，它正如它所說的那樣：當合並兩個集合時，我們總是將較大的集合設定為較小集合的父集合，從而導致最多 步驟的路徑長度 ：

我們在我們的類中儲存了一個額外的成員 std::vector<size_t> size，它被初始化為每個元素的 1。合併兩個集合時，較大的集合成為較小集合的父集合，我們總結了兩個大小：

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }