For the 566D - Restructuring Company

Basic Disjoint Set implementation (w/o ranks) using int vector

class DisjointSet{ public:

    vector <int> parent;

    DisjointSet(int n): parent(n) { for(int i=0; i<n; i++) parent[i] = i; }

    void join(int a, int b) { parent[find(b)] = find(a); }

    int find(int n){
        int par = parent[n];
        if (par != n) par = parent[n] = find(par);
        return par;
    }

    bool check(int a, int b){ return find(a) == find(b); }
};