The problem
Given n nodes numbered 0 to n − 1 and a list of undirected edges, return true if together they form a tree: connected, with no cycles.
Examples
01
- Input
n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
- Output
true
02
- Input
n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
- Output
false
Constraints
- 1 ≤ n ≤ 2000
- 0 ≤ edges.length ≤ 5000
- No self-loops and no repeated edges.
The idea
A tree on n nodes always has exactly n − 1 edges. So first count: any other number, and it is not a tree.
With exactly n − 1 edges, it is a tree precisely when there is no cycle — each of the n − 1 edges then joins two separate groups, bringing n groups down to 1: connected. Union-find spots a cycle as an edge whose ends are already in the same group.
- Time
- O(n · α(n))
- Space
- O(n)
Solution · every language run against every case
class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: # A tree on n nodes has exactly n - 1 edges and no cycle; together those mean connected. if len(edges) != n - 1: return False parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # halve the path as we go x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return False # a and b already joined: this edge makes a cycle parent[ra] = rb return True