# 261 - Graph Valid Tree

解法一 - Union Find

我們可以每遇到一條邊，就把兩個 node union 在一起，然後最後只要 set number 是 1 就好。另外要注意因為是 Tree，所以不能有任何的 cycle，而且每個點都要能走得到，所以 edge 數一定要是 n-1。實作如下：

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if(edges.size() != n-1) {
            return false;
        }         

        // Init for union find
        parent.reserve(n);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
        setNumber = n;

        // Connect all edges
        for(auto e: edges) {
            connect(e[0], e[1]);
        }

        return setNumber == 1;
    }

private:
    int setNumber;
    vector<int> parent;

    void connect(int nodeA, int nodeB) {
        int rootA = find(nodeA);
        int rootB = find(nodeB);

        if(rootA != rootB) {
            parent[rootB] = rootA;
            setNumber--;
        }
    }

    int find(int node) {
        if(node == parent[node])
            return node;

        vector<int> path;
        while(node != parent[node]) {
            path.push_back(node);
            node = parent[node];
        }

        for(auto n: path) {
            parent[n] = node;
        }

        return node;
    }
};

Runtime: 20 ms, faster than 66.35% of C++ online submissions for Graph Valid Tree. Memory Usage: 12 MB, less than 88.89% of C++ online submissions for Graph Valid Tree.