Graph Valid Tree
Medium · Union Find · Depth-First Search · Breadth-First Search · Union Find · Graph
Problem
You have n nodes labeled 0 to n - 1 and a list edges, where edges[i] = [a, b] is an undirected edge between nodes a and b.
Return True if these edges form a valid tree: every node is connected to every other node, and there is no cycle. Otherwise return False.
There are no self-loops and no repeated edges; [0, 1] and [1, 0] are the same edge and never both appear.
Some tests have 20,000 nodes in one long chain, ten times LeetCode's limit. A depth-first search that recurses from node to node goes 20,000 calls deep there and stops with RecursionError. Use union-find, or a search with a queue or an explicit stack.
Examples
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: True
Every node can be reached from node 0, and with exactly n - 1 = 4 edges there is no room for a cycle.
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: False
The edges 1–2, 2–3 and 1–3 form a cycle.
Input: n = 4, edges = [[0,1],[2,3]] Output: False
No cycle, but nodes 0 and 1 cannot reach nodes 2 and 3.
Constraints
- 1 <= n <= 2 * 10^4 (LeetCode stops at 2,000)
- 0 <= len(edges) <= 5 * 10^4
- edges[i] == [a, b], 0 <= a, b < n, a != b
- no edge is listed twice, in either direction
Approaches
- Count the edges, then union-find for cycles — time O(n · α(n)), space O(n)
Follow-up
The edge-count shortcut only works when edges are not repeated. How would you answer if the list could contain duplicates, or if edges arrived one at a time and you had to say after each one whether the graph so far is a forest?
Related problems
Start free on Cariara · Coding problems · System design studio
