# Union Find
Example: [[validate-tree]]. The data structure is a replication of the spanning tree.
```python
class UnionFind(List[int]):
def __init__(self, n):
super().__init__(v for v in range(n))
def __getitem__(self, v):
# returns the root of subtree
while True:
p = super().__getitem__(v)
if v == p:
break
v = p
return v
def union(self, v, w) -> bool:
# returns True if a merge happened
rv = self[v]
rw = self[w]
# same subtree?
if rv == rw:
return False
# rw becomes a child of rv
self[rw] = rv
return True
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
unionFind = UnionFind(n)
return all(unionFind.union(v, w) for v, w in edges)
```