UnionFind.cpp

struct UnionFind
{
    vector<int> p;
    vector<int> ranks;

    UnionFind(int n) : p(n), ranks(n, 0)
    {
        for(int i = 0; i < n; ++i)
            p[i] = i;
    }

    int find_set(int l)
    {
        return (p[l] == l) ? l : (p[l] = find_set(p[l]));
    }

    bool is_same_set(int a, int b)
    {
        return find_set(a) == find_set(b);
    }

    void union_sets(int a, int b)
    {
        int x = find_set(a), y = find_set(b);
        if(is_same_set(x, y))
            return;
        if(ranks[x] > ranks[y])
            p[y] = x;
        else
        {
            p[x] = y;
            if(ranks[x] == ranks[y])
                ranks[y]++;
        }
    }
};