Graph Valid Tree

Graph Valid Tree medium

Description

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_i, b_i] is an undirected edge.

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

A valid tree must be:

Connected — every node is reachable from every other.
Acyclic — no cycles.

Examples

> Case 1:
    n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
    Output: true
 
> Case 2:
    n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
    Output: false   # cycle 1-2-3-1

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
No duplicate edges, no self-loops.

State design

A tree on n vertices has exactly n − 1 edges. So:

If edges.length != n - 1 → not a tree. Done.
Otherwise, run DSU. If any edge connects two already-same-component vertices → cycle → not a tree. Otherwise → tree.

The edge-count shortcut is the cleanest first check. (Without it you’d need to verify connectivity AND acyclicity separately.)

Code

Analysis

Time: O((V + E) · α(V)).
Space: O(V).

Why the edge-count check is so powerful here. With exactly n − 1 edges and no cycles, the graph must be a single component (each successful union reduces component count by 1; starting at n with n − 1 reductions lands at 1). So you don’t need a separate connectivity scan. Three facts: |E| = n − 1, no cycle, exactly one component — knowing any two implies the third.

Same skin

Redundant Connection — given an extra edge, find the one that creates the cycle.
Number of Connected Components — drop the cycle check, keep counting.
Minimum Number of Vertices to Reach All — different angle on the tree concept (directed).

Number of Connected Components Redundant Connection