```
class Solution {
private:
int findParent (int cur, int parent[]) { // find parent with path compression
while (cur != parent[cur])
cur = parent[cur] = parent[parent[cur]];
return cur;
}
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
int parent[n], weight[n];
for (int i = 0; i < n; i++) { parent[i] = i, weight[i] = 1; }
for (auto e : edges) {
int a = findParent(e.first, parent), b = findParent(e.second, parent);
if (a == b) {
return false; // found loop, return false
} else {
if (weight[a] < weight[b]) { swap(a, b); } // always let a to be the heavier one
parent[b] = a, weight[a] += weight[b], n--; // update stats
}
}
return n == 1; // we can only have one parent at last
}
};
```