# Classic C++ Union-Find solution

• Using topological sort to find a circle then use set to find if there is more then one tree seems to be a faster sol, but this is just a classic C++ Union-Find approach, if some one is interested to know.

``````class Solution {
public:
class node{
public:
node(int a) : val(a), parent(&(*this)){}
int val;
node* parent;
};
node* find(node* a){
while(a->parent != a){
a = a->parent;
}
return a;
}

bool join(node* a, node* b){
node* x = find(a);
node* y = find(b);
//cout << x->val << y->val;
if(x == a && y == a){
return false;
}
if(x == b && y == b){
return false;
}

if(x == a){
x->parent = y;
return true;
}
if(y == b){

y->parent = x;
return true;
}
if(x != y){
x->parent = y;
return true;
}
return false;

}

bool validTree(int n, vector<pair<int, int>>& edges) {
if(edges.empty()){
if(n == 1){
return true;
}
return false;
}
map<int, node*> m;
for(int i = 0; i < n; i++){
node* a = new node(i);
m[i] = a;
}
for(int i = 0; i < (int)(edges.size()); i++){

if(!join(m[edges[i].first], m[edges[i].second])){
return false;
}
}
set<node*> s;
for(int i = 0; i < n; i++){
s.insert(find(m[i]));
}
// cout << 123;
return s.size() == 1 ? true : false;

}
};``````

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