lc261-Graph Valid Tree

發表於   |   分類於   |   0 comments   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    vector<int> head;
public:
    bool Union(int node1, int node2) {
        int h1 = node1, h2 = node2;
        while (head[h1] != -1) h1 = head[h1];
        while (head[h2] != -1) h2 = head[h2];
        if (h1 != h2) {
            head[h2] = h1;
            return true;
        }
        else return false;
    }
    bool validTree(int n, vector<pair<int, int>>& edges) {
        for (int i = 0; i < n; i++)  head.push_back(-1);
        for (auto e:edges) {
            if (!Union(e.first, e.second)) return false;
        }
        return (edges.size() == n-1);
    }
};