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.
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. 261. Graph Valid Tree
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<int> nodes(n,0);
for(int i=0; i<n; i++) nodes[i] = i;
for(int i=0; i<edges.size(); i++){
int s = find(nodes,edges[i].first);
int e = find(nodes,edges[i].second);
if(nodes[e] == nodes[s]) return false;
nodes[s] = e;
}
return edges.size() == n-1;
}
int find(vector<int> nodes,int id){
while(id!=nodes[id]){
nodes[id]=nodes[nodes[id]];
id=nodes[id];
}
return id;
}
};