# A simple C++ solution

• share my simple accepted solution:

Thanks for indicating the problem with previous version. The revised version is given below.

``````class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
//use an array to record the root of each node
vector<int> nodes(n, 0);
for(int i = 0 ; i < nodes.size() ; i++){
nodes[i] = i;
}
for(int i = 0; i < edges.size() ; i++){
int root1 = edges[i].first;
int root2 = edges[i].second;
while(nodes[root1] != root1){
root1 = nodes[root1];
}
while(nodes[root2] != root2){
root2 = nodes[root2];
}
if(root1 == root2){
//if two nodes in the edge belong to same node, return false
return false;
}
nodes[root2] = root1;
}
return edges.size() == n-1;
}
};``````

• It is union-set like, but simpler

• I dont think it can handle the case such:
4
[[2,3],[1,2],[1,3]]

• Here's my improvement:

``````class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<int> connect(n,0);
vector<bool> visit(n,false);
if(edges.size()!=n-1) return false;

for(int i=0;i<n;i++){
connect[i]=i;
}
for(int i=0;i<edges.size();i++){

visit[edges[i].first]=visit[edges[i].second]=true;

if(connect[edges[i].first]==connect[edges[i].second]) return false; //detect cycle

connect[edges[i].second]=connect[edges[i].first];
}
for(int i=0;i<n-1;i++)
if (!visit[i]) return false;

return true;
}
};``````

• It still works wrong for the input n=5, [[2,3],[1,2],[1,3],[0,4]]

• 5 [[0,1],[2,1],[2,0],[2,4]] is a similar failure case

• Thanks, you are right. A new version is given. Now the root of each node is derived before the judgement.

• Thanks for your indication. You are right. A new version is given to fix the bug.

• Thanks for the indication. A revised code is given to fix the bug in my answer.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.