234. Graph Valid Tree
You are given n nodes labeled 0 through n - 1 and a list of undirected edges (no self-loops, no repeated edges). Decide whether these edges form a valid tree: a graph that is connected (every node reachable from every other) and acyclic (no cycles). Return true if they do, false otherwise.
A useful fact to prove to yourself first: on n nodes, any two of the three properties — connected, acyclic, exactly n - 1 edges — imply the third. Checking the edge count is free, so you only ever need to verify one structural property.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: true
Explanation: The four edges chain all five nodes into a single path — connected, no cycle, exactly n - 1 edges. A path is a tree.
Example 2:
Input: n = 4, edges = [[0,1],[1,2],[2,0]]
Output: false
Explanation: Nodes 0, 1, 2 close a triangle (a cycle) and node 3 is stranded with no edge at all — this fails on both counts.
Constraints:
- 1 ≤ n ≤ 2000
- 0 ≤ m ≤ 5000
- 0 ≤ u, v < n and u ≠ v
- No edge appears twice (in either direction).
Hints:
Count first: a tree on n nodes has exactly n - 1 edges. If m != n - 1 you can answer false without looking at the graph — and if m == n - 1, connectivity and acyclicity become equivalent, so verify whichever is easier.
Union-Find makes the cycle check one line per edge: union(u, v) fails exactly when u and v were already in the same component, i.e. the edge closes a cycle. Process all edges; with m == n - 1 and no failed union, the graph must be a single connected tree.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Expected output: true