Graph Valid Tree

You're given n vertices labeled 0 to n - 1 and a list of undirected edges. Return true if these edges form a valid tree: all vertices connected, and no cycles.

LeetCode: 261. Graph Valid Tree

Example 1: a tree

graph TB
    0 --- 1
    0 --- 2
    0 --- 3
    1 --- 4

Text

n = 5, edges = [(0,1), (0,2), (0,3), (1,4)]
Output: true

Example 2: has a cycle

graph TB
    0 --- 1
    1 --- 2
    2 --- 3
    1 --- 3
    1 --- 4

Text

n = 5, edges = [(0,1), (1,2), (2,3), (1,3), (1,4)]
Output: false   (1 - 2 - 3 - 1 is a cycle)

The edge count rule

A tree with n vertices has exactly n - 1 edges. That gives a quick first check:

More than n - 1 edges: there must be a cycle.
Fewer than n - 1 edges: the graph can't be connected.

With exactly n - 1 edges, "connected" and "no cycle" imply each other, so it is enough to check one of them. Both solutions below check for a cycle.

Brute force: before each edge, check if its ends are already connected

Add the edges one at a time. An edge (u, v) closes a cycle exactly when u and v are already connected by the edges added so far. Check that with a DFS over the partial graph.

Java

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

public class Main {
    static boolean connected(List<List<Integer>> adj, int a, int b) {
        boolean[] visited = new boolean[adj.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(a);
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (v == b) {
                return true;
            }
            if (!visited[v]) {
                visited[v] = true;
                for (int w : adj.get(v)) {
                    stack.push(w);
                }
            }
        }
        return false;
    }

    static boolean validTree(int n, int[][] edges) {
        if (edges.length + 1 != n) {
            return false;
        }
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            if (connected(adj, u, v)) {
                return false; // this edge would close a cycle
            }
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        return true; // n - 1 edges and no cycle: connected
    }

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

Output

true
false
false

Time: O(E · (V + E)): one DFS per edge. Space: O(V + E).

Optimal: union-find

Union-find (also called disjoint set union) tracks which vertices are in the same connected group, and it answers "are a and b in the same group?" almost instantly. Each group is a small tree of parent links stored in an int array, and the vertex at the top is the group's root, its representative.

find(x): follow parent links from x up to the root.
union(a, b): find both roots. If they're the same, a and b were already connected, so this edge would close a cycle. Otherwise, attach one root under the other, merging the groups.

Two optimizations keep the trees almost flat:

Path halving: during find, point each visited node at its grandparent, which shortens the path for later searches.
Union by size: attach the smaller group under the larger one, so trees stay shallow.

Walkthrough with example 2. Each vertex starts as its own group: {0} {1} {2} {3} {4}.

edge	find(v)	same group?	groups after
(0, 1)	1	no, merge	{0, 1} {2} {3} {4}
(1, 2)	2	no, merge	{0, 1, 2} {3} {4}
(2, 3)	3	no, merge	{0, 1, 2, 3} {4}
(1, 3)	0	yes	cycle: return false

Java

public class Main {
    static class UnionFind {
        private final int[] parent;
        private final int[] size;

        UnionFind(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]]; // path halving
                x = parent[x];
            }
            return x;
        }

        /** Merges the groups of a and b. Returns false if they were already in the same group. */
        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) {
                return false;
            }
            if (size[ra] < size[rb]) {
                int tmp = ra;
                ra = rb;
                rb = tmp;
            }
            parent[rb] = ra; // attach the smaller tree under the larger
            size[ra] += size[rb];
            return true;
        }
    }

    static boolean validTree(int n, int[][] edges) {
        if (edges.length + 1 != n) {
            return false;
        }
        UnionFind uf = new UnionFind(n);
        for (int[] e : edges) {
            if (!uf.union(e[0], e[1])) {
                return false;
            }
        }
        return true;
    }

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

Output

true
false
false
true

Time: O(E · α(V)), which is effectively O(E). α is the inverse Ackermann function, which grows so slowly that it's at most 4 for any input that fits in memory. Space: O(V).

The check edges.length + 1 != n returns false for n = 0 with no edges, since 0 + 1 != 0. A graph with no vertices is not treated as a tree.

Other uses of union-find

Count connected components: start with n groups and subtract one for every successful union.
Kruskal's minimum spanning tree: sort the edges by weight and keep each edge whose union succeeds.
Redundant connection (LeetCode 684): return the first edge whose union fails.