261. Graph Valid Tree

Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], returntrue.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], returnfalse.

S: Union Find O(n)

Valid Tree的条件：

1. 没有环（被连接的两个节点，之前没有直接或间接被连接过）

2. 所有节点都被连接（除了根节点外所有节点都有且只有1条边与父亲相连）

class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        father = vector<int>(n, -1);
        for (const auto& edge : edges) {
            if (!connect(edge.first, edge.second)) {
                return false;
            }
        }
        return edges.size() == n-1;
    }

    bool connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
            return true;
        } else {
            return false;
        }
    }

    int find(int x) {
        if (father[x] == -1) {
            return x;
        }
        return father[x] = find(father[x]);
    }

private:
    vector<int> father;
};