# 9ms 97.08% c++ Union Find solution, applied to all Union Find questions

• ``````class UF{
private:
int count;
int* parent;
int* rank;
public:
UF(int n){
count = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++){
parent[i] = i;
rank[i] = 0;
}
}
~UF(){
delete parent;
delete rank;
}
int find(int x){
while(parent[x] != x){
parent[x] = parent[parent[x]];
x =parent[x];
}
return x;
}
int getCount(){return count;}
bool connected(int x, int y){return find(x) == find(y);}
void connect(int x, int y){
int px = find(x);
int py = find(y);
if (px == py) return;
if (rank[px] > rank[py]) parent[py] = px;
else if (rank[py] > rank[px]) parent[px] = py;
else {
parent[px] = py;
rank[py] ++;
}
count --;
}
};

class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
UF uf = UF(n);
for (auto i :edges){
int x = i.first, y = i.second;
if (uf.connected(x, y)) return false;
uf.connect(x, y);
}
return (uf.getCount() == 1 ? true : false);
}
};
``````

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