Graph Valid Tree
Graph Valid Tree is a medium Graphs problem from the Blind 75. The key pattern is union-find, and a good solution runs in O(E · α(n)) time.
Problem
Determine whether an undirected graph with n labeled vertices is connected and acyclic.
Examples
Example 1
Input
{"n":5,"edges":[[0,1],[0,2],[2,3],[2,4]]}Output
trueExample 2
Input
{"n":5,"edges":[[0,1],[1,2],[2,3],[1,3],[1,4]]}Output
falseExample 3
Input
{"n":1,"edges":[]}Output
trueApproach
A tree on n vertices has exactly n − 1 edges and no cycle. Union the endpoints of each edge and fail if two are already connected.
| Pattern | Union-find |
|---|---|
| Time | O(E · α(n)) |
| Space | O(n) |
Watch out for
Check the edge count first; it rules out most invalid inputs immediately.