1361. Validate Binary Tree Nodes

union-find O(n) time O(n) space
合法的树只有一个连通组件，因为点数和边数之差为1

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        cnt = n;
        for (int i = 0; i < n; ++i) {
            if (!merge(i, leftChild[i])) return false;
            if (!merge(i, rightChild[i])) return false;
        }
        return cnt == 1;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        if (y == -1) return true; // 注意-1的情况！！！
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        --cnt;
        return true;
    }

    int cnt;
    vector<int> parent;
};