Graph Valid Tree
The key idea
An undirected graph on
n nodes is a tree exactly when it has n-1 edges AND is fully connected. With n-1 edges, connectivity already rules out cycles, so checking the edge count plus one reachability sweep (or a union-find that never unions two already-joined nodes) is enough.Problem
You have a graph of n nodes labeled from 0 to n - 1. You are given a list of edges where each edges[i] = [ai, bi] is an undirected edge connecting nodes ai and bi in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise. A valid tree is a graph that is fully connected and contains no cycles.
Constraints
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= ai, bi < nai != bi- There are no self-loops or repeated edges.
Examples
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Complexity
Time: O(n + e) Space: O(n + e)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization