Graph Valid Tree
You get n nodes labeled 0 to n−1 and a list of undirected edges (up to 2000 nodes and 5000 edges, no duplicate edges, no self-loops). Decide whether these edges form a valid tree: a graph that is fully connected (every node reachable from every other) and has no cycles.
Examples
- Input:
- n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
- Output:
- true
All five nodes hang off node 0 (with 4 attached through 1), everything is reachable, and there is no cycle — a valid tree.
- Input:
- n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
- Output:
- false
Nodes 1, 2, 3 form a cycle (1-2-3-1), so this cannot be a tree.
- Input:
- n = 4, edges = [[0,1],[2,3]]
- Output:
- false
No cycle, but the graph is split into two disconnected pieces, so it is not one tree.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.