Graph Valid Tree
MediumGraphs
You get n nodes, numbered 0 to n - 1, and a list of undirected edges, where [a, b] joins node a and node b.
Return true if these edges make a tree: every node is connected to every other, and there is no cycle. Return false otherwise.
Examples
Input: n = 5, edges = [[0, 1], [0, 2], [2, 3], [2, 4]] Output: true
Every node hangs off 0 or 2, all five are connected, and nothing loops.
Input: n = 4, edges = [[0, 1], [1, 2], [2, 0], [2, 3]] Output: false
Nodes 0, 1 and 2 form a loop.
Constraints
1 ≤ n ≤ 20000 ≤ edges.length ≤ 50000 ≤ a, b < nanda ≠ b- No edge appears twice.
Stuck?
Hint 1
A tree on n nodes has exactly n - 1 edges. With that many edges, having no cycle and being connected come to the same thing.
Hint 2
Check the edge count first. Then add the edges to a union-find one by one: an edge whose two ends already share a root closes a cycle.
The idea
A tree on n nodes has exactly n - 1 edges. With exactly that many, a cycle and a node left unconnected always come together, because an edge spent closing a loop is one edge short of joining every node. So check the count, then add the edges one at a time and fail on any edge whose two ends are already connected.
Time O(n log n), with n - 1 edges at mostExtra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Too few edges cannot connect every node, and too many must close a loop. Past this check the count is right, so finding no cycle is enough to prove a tree.
function validTree(n, edges) { if (edges.length !== n - 1) return false; const parent = Array.from({ length: n }, (_, i) => i); const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }; for (const [a, b] of edges) { const rootA = find(a); const rootB = find(b); if (rootA === rootB) return false; parent[rootA] = rootB; } return true;}The trap
This version checks only that there are n - 1 edges. Every tree passes that check, so it looks complete. But n - 1 edges can form a loop in one part of the graph and leave some node with no edge to the rest, and that graph has the right count without being a tree.
function validTree(n, edges) { return edges.length === n - 1; // the right count, but never checks for a cycle or a node left out}