Graph Valid Tree

NeetCode: Graph Valid Tree · LeetCode: 261. Graph Valid Tree · Difficulty: Medium

Given n nodes labeled 0..n-1 and a list of undirected edges, return true if the edges form a valid tree, i.e. the graph is connected and has no cycle.

Example

Text

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]              Output: true
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]        Output: false  (cycle 1-2-3)
n = 4, edges = [[0,1],[2,3]]                          Output: false  (two components)

Brute force: DFS with cycle detection and a connectivity check

A tree is a graph that is connected and has no cycle. Run a DFS from node 0 carrying each node's parent. Seeing an already visited node that is not the parent means a cycle. After the DFS, every node must have been visited, otherwise the graph is disconnected.

The adjacency list is an array of ArrayList<Integer>. The DFS uses an ArrayDeque of int[]{node, parent} pairs as an explicit stack, and -1 stands for "no parent" at the root.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return false;
        }
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[n];
        visited[0] = true;
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{0, -1});
        while (!stack.isEmpty()) {
            int[] top = stack.pop();
            int node = top[0];
            int parent = top[1];
            for (int next : adj.get(node)) {
                if (next == parent) {
                    continue;
                }
                if (visited[next]) {
                    return false;
                }
                visited[next] = true;
                stack.push(new int[]{next, node});
            }
        }
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.validTree(5, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 4}}));
        System.out.println(s.validTree(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}}));
        System.out.println(s.validTree(4, new int[][]{{0, 1}, {2, 3}}));
        System.out.println(s.validTree(1, new int[][]{}));
    }
}

Output

true
false
false
true

The edge back to the parent must be skipped, otherwise every edge looks like a 2-cycle, and the final connectivity check is required to reject disconnected graphs. Skipping by parent label assumes no duplicate edges. Time: O(n + E). Space: O(n + E).

Optimal: the n - 1 edge rule with union-find

A connected graph on n nodes has at least n - 1 edges, and an acyclic one has at most n - 1. So a tree has exactly n - 1 edges, and with that count either property implies the other: no cycle means connected, and connected means no cycle. So check edges.length == n - 1, then union all edges; if any union finds both endpoints already together, there is a cycle. No adjacency list is needed, and a wrong edge count is rejected immediately. The asymptotic cost matches the DFS.

Union-find (a disjoint set union, DSU) keeps each node's parent in an int[]. find returns a set's root and shortens paths as it walks. union attaches the smaller set under the larger one and returns false when both nodes already share a root.

Java

class Dsu {
    private final int[] parent;
    private final int[] size;

    Dsu(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

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

    boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) {
            return false;
        }
        if (size[ra] < size[rb]) {
            int tmp = ra;
            ra = rb;
            rb = tmp;
        }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
}

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n == 0 || edges.length != n - 1) {
            return false;
        }
        Dsu dsu = new Dsu(n);
        for (int[] e : edges) {
            if (!dsu.union(e[0], e[1])) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.validTree(5, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 4}}));
        System.out.println(s.validTree(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}}));
        System.out.println(s.validTree(4, new int[][]{{0, 1}, {2, 3}}));
        System.out.println(s.validTree(1, new int[][]{}));
    }
}

Output

true
false
false
true

The n == 0 check returns first so the comparison with n - 1 only runs for n >= 1. Time: O(n * alpha(n)). Space: O(n).