问题描述：
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.
Example 1:
Input:n = 5, andedges = [[0,1], [0,2], [0,3], [1,4]]Output: true
Example 2:
Input:n = 5,andedges = [[0,1], [1,2], [2,3], [1,3], [1,4]]Output: false
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0]and thus will not appear together in edges.
解题思路：
若一个无向图为一棵树，则图中无环
我们可以用Union Find来确认图中无环
注意：
1. 本题目中给出节点个数，若边的个数为空，说明图中只有节点，若节点个数为0或1，则为一棵有效的树，否则不能构成树
2. 在对每条边进行Union操作后，需要对每一个点进行find来确定每一个点连接到同一个根上。
一开始取根为 int root = find(parents, 0); 而非 int root = parents[0]
代码：
class Solution { public: bool validTree(int n, vector<pair<int, int>>& edges) { if(edges.empty()) return n < 2; vector<int> parents(n); for(int i = 0; i < n; i++) parents[i] = i; for(auto e : edges){ if(!Union(parents, e.first, e.second)) return false; } int root = find(parents, 0); for(int i = 1; i < n; i++){ if(find(parents, i) != root) return false; } return true; } private: int find(vector<int> &parents, int a){ if(parents[a] == a) return a; return parents[a] = find(parents, parents[a]); } bool Union(vector<int> &parents, int a, int b){ int rootA = find(parents, a); int rootB = find(parents, b); if(rootA != rootB){ parents[rootB] = rootA; return true; } return false; } };
原文：https://www.cnblogs.com/yaoyudadudu/p/9190328.html