Park.2018.Spring.DSU

#include <vector>

class DisjointSetUnion {
public:
    DisjointSetUnion(int count);

    //void Set(int v);
    int Find(int v);
    void Union(int set_id1, int set_id2);

private:
    std::vector<int> parent;
    std::vector<int> rank;
};

DisjointSetUnion::DisjointSetUnion(int count)
    : parent(count, 0), rank( count, 1 )
{
    for (int i = 0; i < parent.size(); i++) {
        parent[i] = i;
    }
}

int DisjointSetUnion::Find(int v)
{
    if (v == parent[v]) {
        return v;
    }

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

void DisjointSetUnion::Union(int v, int u)
{
    const int parent_v = Find(v);
    const int parent_u = Find(u);

    if (parent_u == parent_v) {
        return;
    }

    if (rank[parent_v] < rank[parent_u]) {
        parent[parent_v] = parent_u;
    }
    else if (rank[parent_v] > rank[parent_u]) {
        parent[parent_u] = parent_v;
    }
    else {
        parent[parent_u] = parent_v;
        rank[parent_v]++;
    }
}