unionset

//union set
class Djset{
public:
    int count;
    vector<int> parent;
    vector<int> rank;
    Djset(int n): count(n){
        for (int i = 0; i < n; i++){
            parent.push_back(i);
            rank.push_back(0);
        }
    }
    int find(int x){
        if (x == parent[x]) return x;
        else{parent[x] = find(parent[x]);}
        return parent[x];
    }
    bool merge(int x, int y){
        int rx = find(x);
        int ry = find(y);
        if (ry != rx){
            if (rank[rx] < rank[ry]){swap(rx, ry);}
            parent[ry] = rx;
            count --;
            if (rank[rx] == rank[ry]){rank[rx] ++;}
            return false;
        }
        return true;
    }
    
}