Dashboard
#46. Graph Valid TreeMediumGraphs

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

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

Note:

  • You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a_i, b_i < n
  • a_i != b_i
  • There are no self-loops or repeated edges.
Examples
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
Constraints
  • `1 <= n <= 2000`
  • `0 <= edges.length <= 5000`
  • `edges[i].length == 2`
  • `0 <= a_i, b_i < n`
  • `a_i != b_i`
  • There are no self-loops or repeated edges.
Prerequisites
Target: O(N) time • O(1) spaceDepth-First Search / Breadth-First Search / Union Find / Graph
Socratic AI Tutor
Gemini 3.8 Flash
Loading editor...

Click "Run" or press Ctrl+Enter to execute test cases.