74. Graph Valid Tree

Medium · Graph

Given n nodes labeled from 0 to n-1 and a list of undirected edges, determine if these edges form a valid tree.

A valid tree must satisfy two conditions: (1) it has exactly n-1 edges, and (2) all nodes are connected in a single component with no cycles.

Return true if the edges form a valid tree, false otherwise.

Examples

Example 1
Input: n = 4, edges = [[0,1], [0,2], [0,3]]
Output: true
Explanation: The edges form a star graph centered at node 0, connecting all 4 nodes with 3 edges and no cycles. This is a valid tree.
Example 2
Input: n = 5, edges = [[0,1], [1,2], [2,3], [1,3]]
Output: false
Explanation: There are 4 edges for 5 nodes (should be 4 edges for a tree with 5 nodes), but nodes 1, 2, 3 form a cycle (1→2→3→1), so this is not a valid tree.

Constraints