Graph Valid Tree
Given n nodes labelled 0 to n − 1 and a list of undirected edges, decide whether they form a valid tree.
A way to picture it
Union-Find is a club membership desk. Everyone starts in their own club. Each edge merges two clubs. But if an edge tries to join two people who are already in the same club, it's building a second road between them — a loop — and trees don't have loops.
How to approach it
A tree has exactly n − 1 edges and no cycle. Check the count, then union every edge; if two endpoints already share a root, there's a cycle.
Example
Input: {"n":5,"edges":[[0,1],[0,2],[0,3],[1,4]]}. Output: true.
Complexity: O(n · α(n)) time and O(n) space. Near-constant time per union/find with path compression.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.