Graph Valid Tree

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True