Union-Find · 144Medium
Graph Valid Tree
Given n nodes labelled 0..n-1 and a list of undirected edges, determine whether they form a valid tree: fully connected and containing no cycles.
Constraints
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- There are no self-loops or repeated edges.
Examples
validTree(5, [[0,1],[0,2],[0,3],[1,4]]) -> true validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]) -> false // has a cycle validTree(2, []) -> false // disconnected validTree(1, []) -> true // single node, no edges validTree(3, [[0,1],[1,2]]) -> true // a path is a tree validTree(4, [[0,1],[1,2],[0,2]]) -> false // n-1 edges, still not connected
Edge cases
- A tree on n nodes has EXACTLY n - 1 edges.
- Correct edge count is not sufficient; it must also be connected.
- A single node with no edges is a valid tree.
Show the target complexity (spoiler)
- Naive
- Checking connectivity and cycles with two independent passes duplicates work.
- Target
- O(E * a(N)) with union-find — reject if any union joins two nodes already in the same set, then confirm exactly one set remains.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/18-union-find/144-graph-valid-tree.js ./practice c 144