The machine must decide whether an undirected graph on n nodes is a valid tree. A tree is exactly two things: connected and acyclic. Any graph with n nodes that is connected and acyclic necessarily has exactly n - 1 edges, which gives the machine a cheap first filter.
The key insight is that union-find detects both properties in one pass over the edges. While processing an edge, if its two endpoints are already in the same component, adding it creates a cycle — the graph is not a tree. If no edge triggers that and the edge count is exactly n - 1, the graph is automatically connected.
The approach has three steps. First, reject immediately if the edge count is not n - 1, since such a graph can be neither acyclic nor connected. Second, run union-find over all edges, checking before each union whether the endpoints share a root; if they do, return false. Third, after all edges process without a cycle, return true — the n - 1 count guarantees connectivity. Time is O(n × α(n)) with path compression, essentially linear, and space is O(n).
The trickiest edge case is the disconnected forest: n = 4 with edges forming two separate pairs. The count is exactly 2, passes the first filter, and no cycle exists — yet the graph is not connected. Only the combined count-plus-cycle logic catches it.
def validTree(n, edges):
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb:
return False
parent[ra] = rb
return True