Graph Valid Tree

Problem#

Given n nodes labeled 0..n-1 and a list of undirected edges, decide whether the graph forms a valid tree.

Examples#

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → true
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] → false (cycle)

Constraints#

1 <= n <= 2000, 0 <= edges.length <= 5000, no self-loops or duplicate edges.

Approach#

A tree has exactly n - 1 edges and is connected (and equivalently, has no cycle). Union-find each edge; if any edge connects already-unioned vertices, there’s a cycle. At the end, the number of edges must be n - 1 (equivalently, all nodes share one root).

Solution#

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if ((int)edges.size() != n - 1) return false;
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        function<int(int)> find = [&](int x) {
            while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
            return x;
        };
        for (auto& e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) return false;
            parent[a] = b;
        }
        return true;
    }
};

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 {
        return false
    }
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    for _, e := range edges {
        a, b := find(e[0]), find(e[1])
        if a == b {
            return false
        }
        parent[a] = b
    }
    return true
}

from typing import List

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

function validTree(n, edges) {
    if (edges.length !== n - 1) return false;
    const parent = Array.from({ length: n }, (_, i) => i);
    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    for (const [a, b] of edges) {
        const ra = find(a), rb = find(b);
        if (ra === rb) return false;
        parent[ra] = rb;
    }
    return true;
}

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 a = find(e[0]), b = find(e[1]);
            if (a == b) return false;
            parent[a] = b;
        }
        return true;
    }

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

function validTree(n: number, edges: number[][]): boolean {
    if (edges.length !== n - 1) return false;
    const parent: number[] = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (const [a, b] of edges) {
        const ra = find(a), rb = find(b);
        if (ra === rb) return false;
        parent[ra] = rb;
    }
    return true;
}

Editorial#

The edges.size() == n - 1 short-circuit rules out both too-few-edges (disconnected) and too-many-edges (must contain a cycle). Union-find then verifies that each edge connects two previously separate components — equivalently, no cycle.

Complexity#

Time: O((V + E) * α(V)).
Space: O(V).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#