196. Graph Valid Tree

A graph is a tree exactly when it is connected and acyclic. With exactly n-1 edges, 'no cycle' already guarantees 'connected', so union-find just has to reject any edge whose endpoints are already joined.

Two conditions collapse into one check

A valid tree on n nodes has exactly n-1 edges and no cycle. Given n-1 edges, being acyclic forces connectivity (a forest with n-1 edges and no cycle is a single tree). So:

1. If len(edges) != n - 1, return false immediately.
2. Union-find each edge; if an edge connects two nodes already in the same set, that's a cycle → return false.
3. Survive all edges → true.

Walk-through

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]: 4 edges = n-1. Each union joins new nodes, no repeated roots → true.

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]: 5 edges ≠ 4 → false (too many edges means a cycle).

Complexity

• Time: O((n + e)·α(n)).
• Space: O(n).

class Solution {
    private int[] parent;

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return false;  // cycle
            parent[ra] = rb;
        }
        return true;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}