Topics › Graphs › Problems on BFS/DFS

Graph Valid Tree

Medium TUF ID 495 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given n vertices labelled 0 to n - 1 and a list of undirected edges, where [a, b] joins a and b. Return true if these edges make the vertices into one valid tree: a graph that is connected and has no cycle.

Constraints: 1 ≤ n ≤ 2000, 0 ≤ edges.length ≤ 5000, no duplicate edges ([0,1] and [1,0] never both appear).

Example 1

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
answer = true       // connected, 4 edges on 5 vertices, no loop

Example 2

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
answer = false      // 1 - 2 - 3 - 1 is a cycle

Three equivalent descriptions of a tree on n vertices are worth knowing, because each approach below uses a different one:

1. Connected and acyclic.
2. Connected, and every edge is a bridge (removing any edge disconnects the graph).
3. Connected with exactly n - 1 edges, or equally, acyclic with exactly n - 1 edges.

The edge count is the shortcut. Adding edges one at a time to n isolated vertices, each edge either merges two components (count drops by one) or closes a cycle. Reaching a single component without a cycle takes exactly n - 1 merges.

Approach 1: Brute force, connected and every edge is a bridge

Intuition. Use description 2 directly. First check that one BFS from vertex 0 reaches all n vertices. Then, for each edge u - v, rebuild the graph without it and test whether v is still reachable from u. If it is, there was another route, so the edge lies on a cycle and the graph is not a tree. If every edge is a bridge, the graph is connected and acyclic.

Algorithm.

1. If a BFS from 0 does not reach all n vertices, return false.
2. For each edge u - v: a self-loop (u == v) is a cycle, so return false; otherwise BFS from u without this edge and return false if v is reached.
3. Return true.

static boolean bruteForce(int n, int[][] edges) {
    if (countReachable(n, edges, -1, 0) != n) return false;   // must be connected
    for (int skip = 0; skip < edges.length; skip++) {
        int u = edges[skip][0], v = edges[skip][1];
        if (u == v) return false;                     // a self-loop is a cycle
        if (reachableWithout(n, edges, skip, u, v)) return false;   // another route: the edge sits on a cycle
    }
    return true;
}

/** Number of vertices reachable from start when edge number skip is ignored. */
static int countReachable(int n, int[][] edges, int skip, int start) {
    boolean[] seen = bfs(n, edges, skip, start);
    int count = 0;
    for (boolean b : seen) if (b) count++;
    return count;
}

static boolean reachableWithout(int n, int[][] edges, int skip, int from, int to) {
    return bfs(n, edges, skip, from)[to];
}

static boolean[] bfs(int n, int[][] edges, int skip, int start) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int i = 0; i < edges.length; i++) {
        if (i == skip) continue;
        adj.get(edges[i][0]).add(edges[i][1]);
        adj.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] seen = new boolean[n];
    Deque<Integer> queue = new ArrayDeque<>();
    seen[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int x = queue.poll();
        for (int y : adj.get(x)) {
            if (!seen[y]) {
                seen[y] = true;
                queue.add(y);
            }
        }
    }
    return seen;
}

Complexity. Time O(E · (n + E)): a full graph rebuild and BFS per edge. Space O(n + E) for the adjacency list. With n = 2000 and E = 5000 this is around 3.5 · 10^7 steps, which passes, but it does far more work than needed.

Approach 2: Optimal, count edges and check connectivity with one BFS

Intuition. Description 3 needs only two facts: the number of edges and whether the graph is connected. The count is free: if edges.length != n - 1, answer false immediately. With exactly n - 1 edges, a single BFS from vertex 0 settles the rest. If it reaches all n vertices, the graph is connected, and a connected graph with n - 1 edges is a tree. If it does not, the graph is disconnected, and it must also contain a cycle somewhere: n - 1 edges spread over two or more components means at least one component has as many edges as vertices.

There is no need to look for cycles explicitly. The edge count does that job.

Algorithm.

1. If edges.length != n - 1, return false.
2. BFS from vertex 0 over all edges and count the reached vertices.
3. Return whether the count equals n.

static boolean optimalBfs(int n, int[][] edges) {
    if (edges.length != n - 1) return false;          // a tree on n vertices has exactly n - 1 edges
    return countReachable(n, edges, -1, 0) == n;
}

Complexity. Time O(n + E): building the adjacency list and one BFS. Space O(n + E).

The test n = 4, edges = [[0,1],[1,2],[2,0]] shows why both checks are needed. It has exactly n - 1 = 3 edges, but the triangle leaves vertex 3 isolated. The BFS from 0 reaches only three vertices, so the answer is false.

Approach 3: Optimal, union-find

Intuition. Process the edges one at a time while maintaining the connected components in a disjoint-set (union-find) structure. For an edge u - v, find the representatives of both endpoints. If they are already the same, u and v were already connected, so this edge closes a cycle: return false. Otherwise, merge the two sets. Combined with the n - 1 check, n - 1 successful merges starting from n singleton sets leave exactly one set, which means the graph is connected. No adjacency list is built at all.

This version is handy when the edges arrive as a stream, or when the graph is too large to want an adjacency list. With union by size and path halving, each find is effectively constant time.

Algorithm.

1. If edges.length != n - 1, return false.
2. Make every vertex its own set (parent[i] = i, size[i] = 1).
3. For each edge: a = find(u), b = find(v). If a == b, return false. Otherwise attach the smaller set’s root under the larger one.
4. Return true.

static boolean optimalUnionFind(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] parent = new int[n], size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    for (int[] e : edges) {
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) return false;                     // u and v already connected: this edge closes a cycle
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;                                // union by size
        size[a] += size[b];
    }
    return true;                                      // n - 1 merges leave exactly one set
}

static int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];                // path halving
        x = parent[x];
    }
    return x;
}

Dry run on example 2. The edge count is 5, not n - 1 = 4, so union-find returns false immediately. To see the cycle check at work, run the loop anyway:

Complexity. Time O(n + E · α(n)), where α is the inverse Ackermann function, below 5 for any practical n. Space O(n) for parent and size.

Edge cases and pitfalls

• A single vertex with no edges is a tree. n = 1, edges = [] returns true; n - 1 = 0 edges is correct.
• Isolated vertices. n = 2, edges = [] is not a tree: two components.
• Right count, wrong shape. n - 1 edges can still form a cycle plus an isolated vertex, so the count alone is never enough; pair it with connectivity or with the union-find cycle check.
• Forests. n = 4, edges = [[0,1],[2,3]] has no cycle but two components, so it is not a tree. Approaches 2 and 3 reject it on the edge count.
• Self-loops. [0, 0] is a cycle. Union-find sees find(0) == find(0), the brute force checks it explicitly, and the BFS version notices that the self-loop wastes an edge, so the graph cannot be connected.
• Undirected edges. Add both directions to the adjacency list. Adding only a -> b makes the BFS miss vertices reachable only “backwards”.
• Union by size and path compression keep find fast. Without them a long chain of unions can make find linear, which is fine for 2000 vertices but bad habits for larger inputs.

Related problems

• Detect A cycle in Undirected Graph using BFS is the “acyclic” half of this problem on its own.
• Detect A cycle in Undirected Graph using DFS does the same with DFS.
• Connected Components is the “connected” half: count components.
• Disjoint Set explains union by size and path compression in depth.
• Number of operations to make network connected uses the same union-find counting of spare edges and components.