Graph Valid Tree

Given n nodes and an undirected edge list, determine whether the graph is a valid tree. A tree must be connected and acyclic, so DSU cycle checks and component counting both matter.

Input Format

n = number of nodes, edges = undirected edges

Output Format

true if the graph is a valid tree

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 5
edges = [[0,1],[0,2],[0,3],[1,4]]

Output:

true

Explanation:

The graph has 5 nodes, 4 edges, no cycle, and is connected.

Example 2:

Input:

n = 5
edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

Output:

false

Explanation:

The edge [1,3] creates a cycle.

Example 3:

Input:

n = 4
edges = [[0,1],[2,3]]

Output:

false

Explanation:

The graph is disconnected.

Loading...
Graph Valid Tree - Union Find DSA Problem