Graph Valid Tree

Problem

You are given n nodes labelled 0 to n - 1 and a list of undirected edges, each a pair [u, v]. Decide whether these edges form a tree over all n nodes: the graph must be connected and contain no cycle.

• There are at most 3,000 nodes and at most 8,000 edges.
• No self-loops, and each unordered pair appears at most once.

Examples

• n = 6, edges = [[0,1],[0,2],[1,3],[1,4],[4,5]] → true. Five edges, all six nodes connected, no cycle.
• n = 6, edges = [[0,1],[1,2],[2,3],[3,1],[4,5]] → false. Nodes 1, 2, 3 form a triangle, and node 0's part is a separate piece from {4,5}.
• n = 5, edges = [[0,1],[2,3]] → false. No cycle, but node 4 is isolated and {0,1}, {2,3} are two more separate components.

Hints

1. How many edges does a tree on n nodes have? What can you conclude if the count is wrong?
2. Given the right number of edges, only one of "connected" and "acyclic" still needs to be checked. Why?
3. Union-find: process each edge; if both endpoints already share a root, the edge closes a cycle. With exactly n-1 edges and no cycle, the graph is automatically connected.