Given n nodes labeled from 0 to n - 1 and 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:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
思路：union find。
是一个树的条件有两个：无环，边数等于节点数减一。
检测无环可以用union find：枚举所有的边，检测并更新他们端点所属的集合。一开始所有的节点都属于各自的集合，然后merge每个边两端点所在的集合。因为树中的点都是连在一起的，最后肯定会在一个集合。注意的是，如果有一条边，一旦将它添加到树中后就会构成一个环，那么这条边的两个端点一定之前已经被添加进了树中（两个点属于同一个集合），否则，每条新加的边，至少有一个端点是之前不存在于这棵树中的（两个点属于不同的集合）。
class Solution {
public:
int find(vector<int> &parent, int x) {
if (parent[x] == x) return x;
int pa = find(parent, parent[x]);
parent[parent[x]] = pa;
return pa;
}
void merge(vector<int> &parent, int x, int y) {
int parentX = find(parent, x);
int parentY = find(parent, y);
if (parentX != parentY)
parent[parentY] = parentX;
}
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<int> parent(n, );
for (int i = ; i < n; i++) parent[i] = i;
for (int i = ; i < edges.size(); i++) {
if (find(parent, edges[i].first) == find(parent, edges[i].second))
return false;
merge(parent, edges[i].first, edges[i].second);
}
return n - == edges.size();
}
};