根据规模改进联合

在我们当前的 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
    }