Union Find

class UnionFind {
    vector<int> rank, parent;
public:
    int numSets;
    UnionFind(int size) {
        rank.assign(size, 1);
        parent.resize(size);
        for(int i = 0; i < size; i++) parent[i] = i;
        numSets = size;
    }

    int findSet(int i) {
        if(parent[i] == i) return i;
        return parent[i] = findSet(parent[i]);
    }

    void unionSet(int i, int j) {
        int x = findSet(i), y = findSet(j);
        if(x == y) return;

        numSets--;
        if(rank[y] > rank[x]) swap(x, y);
                
        if(rank[x] == rank[y]) {
            rank[x]++;
            parent[y] = x;
        }
        else {
            parent[y] = x;
        }
    }
};