Graph Valid Tree

First reject immediately if there are not exactly n - 1 edges — too few can’t connect everything, too many guarantees a cycle. Otherwise, build an adjacency list and DFS from node 0, tracking each node’s parent in the DFS tree so that walking back along the edge you just came from is not mistaken for a cycle. If DFS reaches an already-visited node that is not the immediate parent, that is a genuine cycle. Afterward, check that DFS reached all n nodes.

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()

        def dfs(u, parent):
            visited.add(u)
            for v in graph[u]:
                if v == parent:
                    continue
                if v in visited:
                    return False
                if not dfs(v, u):
                    return False
            return True

        if not dfs(0, -1):
            return False
        return len(visited) == n

On the example: edge count check passes (4 == 5 - 1). dfs(0, -1) visits 0, then walks to 1 (dfs(1, 0)), which walks to 4 (dfs(4, 1), a dead end) and back to 0 — but 0 is 1’s parent, so that’s skipped, not flagged as a cycle. Back at 0, DFS continues to 2 and 3, both dead ends. All 5 nodes end up visited with no cycle found, so the result is True.

Why it’s correct: the n - 1 edge count rules out both “too sparse to connect” and “too dense to be acyclic” in one comparison; the parent-aware DFS then confirms both remaining properties in a single pass — reaching an already-visited non-parent node proves a cycle, and len(visited) == n proves connectivity. Complexity: the adjacency list is built in O(E) and DFS visits each node and edge once → O(V + E) time, O(V + E) space for the graph, visited set, and recursion stack.

Process edges one at a time, unioning the two endpoints’ components. If an edge ever connects two nodes that are already in the same component, that edge closes a cycle — immediate False. If every edge unions two previously-separate components, and there are exactly n - 1 of them, all n nodes have been merged into a single component by construction, so connectivity is guaranteed without a separate check.

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path compression
                x = parent[x]
            return x

        def union(x, y):
            root_x, root_y = find(x), find(y)
            if root_x == root_y:
                return False  # already connected -> this edge creates a cycle
            parent[root_x] = root_y
            return True

        return all(union(a, b) for a, b in edges)

Run the trace on the example (n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]). Watch the mechanism that makes the algorithm work — before every edge, find climbs the parent arrows to each endpoint’s root, and a union is allowed only when those two roots differ:

All four edges merged different roots, so no cycle formed and every union succeeded — the parent chain ends as 0 → 1 → 2 → 3 → 4. Count the components from the start: 5 singletons, and each successful union reduces that count by 1, so 4 successful unions leave exactly one component — connected and acyclic, a valid tree.

The edge-count check cannot see every cycle, though. This second run uses exactly 4 edges on the same 5 nodes, so the gate passes — but edge (2, 0) will try to connect two nodes that already share a root. Watch both find climbs land on root 3:

The shared root makes union return False, so all(...) short-circuits and the answer is False immediately. (The statement’s second example — five edges on five nodes — is caught even earlier by the len(edges) != n - 1 check, before the loop ever runs.) Every successful union merges two previously-separate components, so with n - 1 successful edges and no cycle, all n nodes are guaranteed to sit in one component.

Why it’s correct: two nodes share a root if and only if they are already connected through previously-processed edges; unioning them anyway would add a redundant, cycle-creating connection. Requiring exactly n - 1 edges and every union to succeed means every edge strictly grows the number of connected nodes by one, which forces full connectivity by the time all edges are processed. Complexity: n - 1 union-find operations, each nearly O(1) amortized with path compression → O(V + E) time (effectively O(V · α(V))), and O(V) space for the parent array — no adjacency list needed at all, which is why this is the leaner approach.