Graph Valid Tree
Medium
Depth-First Search
Breadth-First Search
Union Find
Graph
You have a graph of `n` nodes labeled from `0` to `n - 1`. You are given an integer `n` and a list of `edges` where `edges[i] = [aᵢ, bᵢ]` indicates that there is an undirected edge between nodes `aᵢ` and `bᵢ` in the graph. Return `true` *if the edges of the given graph make up a valid tree, and* `false` *otherwise*.
Example 1
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Example 2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Example 3
Input: n = 1, edges = []
Output: true

Constraints

  • •1 <= n <= 2000
  • •0 <= edges.length <= 5000
  • •edges[i].length == 2
  • •0 <= aᵢ, bᵢ < n
  • •aᵢ != bᵢ
  • •There are no self-loops or repeated edges.
Time Complexity
O(V+E)
Space Complexity
O(V+E)
14
Case 1
Input: 5 [[0,1],[0,2],[0,3],[1,4]]
Expected: true
Case 2
Input: 5 [[0,1],[1,2],[2,3],[1,3],[1,4]]
Expected: false
Case 3
Input: 1 []
Expected: true