DSA problem
Graph Valid Tree
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, b] indicates that there is an undirected edge between nodes a and b in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise.
A connected undirected graph on n nodes is a tree if and only if it satisfies two conditions simultaneously: it has exactly n - 1 edges, and it contains no cycles. These two facts together also imply connectivity, because any acyclic graph with n - 1 edges on n nodes must be connected (a missing edge would force one of the components to have fewer than n_i - 1 edges, which is impossible for an acyclic component).
This makes Union-Find an extremely clean fit. Start with every node in its own component. For each edge (a, b), attempt to union them: if find(a) == find(b) already, the edge would close a cycle and we return false. Otherwise the union merges two components. After processing all edges, every node should belong to one component — equivalent to checking that we have exactly n - 1 edges (which is the simpler form once the cycle check has passed).
Using path compression and union-by-rank keeps each operation effectively O(α(n)) (inverse Ackermann), so the total time is essentially O(n + e) and the space is O(n) for the parent and rank arrays.
Examples
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]truen = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]falsen = 4, edges = [[0,1],[2,3]]falseConstraints
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= a, b < n
- a != b
- There are no self-loops or repeated edges.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.