#261

Graph Valid Tree

medium· Graphsruns: 0

You have an undirected graph of n nodes labeled 0 to n - 1. You are given the integer n and an array of edges where each edges[i] = [a, b] indicates an undirected edge between a and b. Return true if the edges form a valid tree (connected and acyclic with exactly n - 1 edges).

wpm 0acc 100%time 0:000 / 503

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: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            parent[ra] = rb
        return True

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.