Union Find

Example: validate-tree. The data structure is a replication of the spanning tree.

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)