gistfile1.txt

// inspired by https://algorithms.tutorialhorizon.com/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/
class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;     //Union by rank
    
public:
    int count;
    
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n);
        count = n;
        for(int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]); //path compression
        }
        return parent[x];
    }
    
    bool addUnion(int x, int y) {
        int X = find(x); int Y = find(y);
        if(X == Y) return false;
        if(rank[X] > rank[Y]) parent[Y] = X;    //tree Y is lower
        else if(rank[X] < rank[Y]) parent[X] = Y; // tree X is lower
        else { // same height
            parent[Y] = X;
            rank[X]++;
        }
        count--;
        return true;
    }
};
class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        UnionFind *uf = new UnionFind(n);    
        for(auto &e : edges) {
            if(!uf->addUnion(e[0], e[1])) return false;
        }
        return uf->count == 1;
    }
};