# Validate [[tree|Tree]]
Also see [[cycle-detection]].
- Conditions
- `n - 1` edges
- Connected (can be checked using [[union-find]])
## Union Find Approach
Visit [[union-find]] for the actual UnionFind data structure implementation.
```python
if len(edges) != n - 1:
return False
forest = [[v] for v in range(n)]
for v, w in edges:
# each new edge should connect two trees
if forest[v] is forest[w]:
return False
forest[v] += forest[w]
for s in forest[w]:
forest[s] = forest[v]
n -= 1
return n == 1
```
Time complexity is between $\Omega(n)$ and $O(n^2)$.
Alternatively, use customized class.
```python
class Tree(set):
def __hash__(self):
return id(self)
def __eq__(self, other):
return self is other
forest = set([Tree([v]) for v in range(n)])
...
v_tree |= w_tree
forest.remove(w_tree)
...
```
Since merging is taking $O(|S_2|)$, this is still not efficient.