Validate 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.

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.

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.