按大小联合中不相交集联合路径压缩的后果

Question

按大小进行合并时，您可以比较要统一的节点的大小。我在 codeforces 上找到了这段代码，它展示了如何构建具有路径压缩和按大小联合的 DSU：

#include <bits/stdc++.h>
using namespace std;

class DSU
{
public:
    unordered_map<int, int> parent;
    unordered_map<int, int> size;

    void make_set(int v)
    {
        parent[v] = v;
        size[v] = 1;
    }

    int find_set(int v)
    {
        if (v == parent[v])
            return v;

        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);

        if (a != b)
        {
            if (size[a] < size[b])
                swap(a, b);

            // a big, b small
            // attach small tree to big tree
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

问题是，您是否必须进行修改find_set以减小父节点的大小，因为父节点现在将指向根而不是另一个子节点？

这不是正确的实现吗find_set？

    int find_set(int v)
    {
        if (v == parent[v])
            return v;

        size[parent[v]] -= 1;
        return parent[v] = find_set(parent[v]);
    }

Answer 1

是的，但是您没有任何收获，因为该父级不是该集合的代表。

那是，

int find_set(int v)
{
    if (v == parent[v])
        return v;
    
    // This parent is not the representative, changing
    // the size is superfluous as it will no longer 
    // be referenced again.
    size[parent[v]] -= 1;
    return parent[v] = find_set(parent[v]);
}