Design Gurus Logo
Blind 75
Graph Valid Tree (medium)

Problem Statement

Given a number n, which indicates the number of nodes numbered from 0 to n-1, and a list of undirected edges for the graph, determine if the graph is a valid tree.

A graph qualifies as a valid tree if it meets the following criteria:

  1. It has no cycles.
  2. It is fully connected.

Examples

  • Example 1:

    • Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Image

  • Expected Output: true

  • Justification: There are no cycles in the graph, and all nodes are connected, forming a valid tree.

  • Example 2:

    • Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]]]
Image

  • Expected Output: false

  • Justification: There is a cycle in the graph (0-1-2-3-0), thus it's not a valid tree.

  • Example 3:

    • Input: n = 5, edges = [[0,1],[1,2],[2,3]]
Image

  • Expected Output: false

  • Justification: TNode 4 is not connected to any other node, making the graph not fully connected.

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a<sub>i</sub> <= b<sub>i</sub> < n
  • a<sub>i</sub> != b<sub>i</sub>
  • There are no self-loops or repeated edges.

Try it yourself

Try solving this question here:

Python3
Python3