Mid/Senior
Graph Valid Tree
You have a graph of n nodes labeled from 0 to n - 1. You are given an array edges, where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi.
Return true if the given edges form a valid tree, and return false otherwise.
A graph is a valid tree if:
- It is connected, meaning every node can be reached from every other node.
- It has no cycles.
Example 1
Input
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]Output
trueAll 5 nodes are connected and there is no cycle, so the graph is a valid tree.
Example 2
Input
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]Output
falseThe edges [1, 2], [2, 3], and [1, 3] form a cycle, so the graph is not a valid tree.
Constraints
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- There are no repeated edges