Description

Submission

class UnionFind {
    vector<int> uf;
public:
    int count;

    UnionFind(int n) {
        uf.resize(n);
        for(int i = 0; i < n; ++i) {
            uf[i] = i;
        }
        count = n;
    } 

    void connect(int a, int b) {
        int ai = find(a);
        int bi = find(b);
        uf[ai] = bi;
        count--;
    }

    int find(int a) {
        if(uf[a] == a) return a;
        return find(uf[a]);
    }
};

class Solution {
    
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        UnionFind uf(n);
        for(auto e: edges) {
            if(uf.find(e[0]) == uf.find(e[1])) 
                return false;
            else {
                uf.connect(e[0], e[1]);
            }
        }
        return uf.count == 1;
    }
};