Start learning free

LESSON 470 OF 536 · GRAPHS

Graph Valid Tree in Java: Union-Find in Nearly O(n + e)

Practice O((n + e)·α(n)) Read the full explanation

You have a graph of n nodes, numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi] means that there is an undirected edge between nodes ai and bi.

The graph is a tree when it is connected (you can get from any node to any other by following edges) and has no cycle (no path of edges leads from a node back to itself without using an edge twice). Put another way, there is exactly one path between any two nodes.

Return true if the edges make the graph a valid tree, or false otherwise.

 

Example 1:

Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true
Explanation: Every node can be reached from node 0, and no edge closes a cycle:
        0
      / | \
     1  2  3
     |
     4

Example 2:

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false
Explanation: The edges 1 - 2, 2 - 3 and 1 - 3 form a cycle, so there are two paths from 1 to 3.

Example 3:

Input: n = 4, edges = [[0, 1], [1, 2], [2, 0]]
Output: false
Explanation: There are 3 edges for 4 nodes, the number a tree of 4 nodes has, but the edges
0 - 1, 1 - 2 and 2 - 0 form a cycle, and node 3 has no edge at all. Counting the edges is not enough.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated edges.

Note:

Your algorithm should run in O((n + e)·α(n)) time, nearly O(n + e), where e is the number of edges, and use O(n) extra space.

A tree with n nodes has exactly n - 1 edges. With that many edges, the graph is a tree exactly when no edge closes a cycle, because then every edge joins two separate groups and the n single nodes end up as one group. The tutorial checks the count first, then adds the edges one by one with union-find, as in Number of Connected Components in an Undirected Graph: an edge whose two nodes are already in the same group closes a cycle. With path halving and union by size, each step costs O(α(n)) on average, where α is the inverse Ackermann function, below 5 for any n a computer can hold.

A DFS or BFS from node 0 that checks that every node is reached also works in O(n + e) once the count is right; on a graph this big, use a BFS or a DFS with its own stack, since a recursive DFS down a path of 105 nodes can run out of call stack.

STEP 1 OF 21
    Ctrl + Enter to check

    JAVA · GRAPHS

    Graph Valid Tree in Java, explained

    Problem overview

    The method validTree receives n, the number of nodes (numbered 0 to n - 1), and edges, an array of pairs where each pair is an undirected edge. It returns true when these edges make the graph a tree and false otherwise. A graph is a tree when it is connected, so you can get from any node to any other, and has no cycle. Equivalently, there is exactly one path between any two nodes.

    For n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]] the answer is true: every node is reachable from node 0 and no edge closes a loop. For n = 5 and [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] it is false, because the edges 1-2, 2-3 and 1-3 form a cycle. For n = 4 and [[0, 1], [1, 2], [2, 0]] it is false as well: there are 3 edges, the number a tree of 4 nodes needs, but they form a cycle and node 3 is cut off.

    The statement asks for O((n + e) · α(n)) time, nearly O(n + e), where e is the number of edges, and O(n) extra space. With n and e up to 100,000, the solution has to be near linear.

    Approach: count the edges, then look for a cycle

    A tree with n nodes has exactly n - 1 edges. Fewer edges leave some node cut off from the rest. More edges must close a cycle. So the first check is simply edges.length != n - 1.

    With exactly n - 1 edges, the graph is a tree precisely when no edge closes a cycle. The reason is that every edge that joins two separate groups of nodes lowers the number of groups by one. Starting from n single nodes, n - 1 such edges leave one group, which means the graph is connected. Example 3 shows why the count alone isn't enough: it has the right number of edges but one of them closes a loop.

    To find a cycle, process the edges one by one with union-find (also called disjoint sets). It keeps every group of connected nodes as a small tree of parent pointers, and the root, the node that is its own parent, names the group. For an edge, find the root of each end. If the roots are equal, the ends are already connected through other edges, and this edge adds a second path between them: a cycle. If the roots differ, merge the two groups.

    Two refinements keep the cost nearly constant per operation. Union by size always hangs the smaller tree under the larger one. Path halving makes each node visited during a lookup point to its grandparent, so later lookups are shorter. Together, each operation costs O(α(n)) on average, where α is the inverse Ackermann function, which stays below 5 for any n a computer can hold.

    A breadth-first or depth-first search from node 0 that checks every node was reached also works once the edge count is right. This lesson uses union-find, and its lookup is a loop rather than a recursion, so a path of 100,000 nodes causes no stack problem.

    Here is the state after each edge of the first example, showing the parent and size arrays:

    [0, 1] parent=[0, 0, 2, 3, 4] size=[2, 1, 1, 1, 1]
[0, 2] parent=[0, 0, 0, 3, 4] size=[3, 1, 1, 1, 1]
[0, 3] parent=[0, 0, 0, 0, 4] size=[4, 1, 1, 1, 1]
[1, 4] parent=[0, 0, 0, 0, 0] size=[5, 1, 1, 1, 1]

    Each edge joins two different groups, and at the end all five nodes lead to root 0. For the third example (n = 4), the edges [0, 1] and [1, 2] merge groups, and for [2, 0] both ends have root 0, so the method returns false.

    Step by step

    1. Check the edge count. If edges.length != n - 1, return false.
    2. Create parent, an int array of size n, where parent[x] is the parent of node x.
    3. Create size, another array of size n. size[r] counts the nodes in the group with root r. Only the roots' entries stay up to date, and they decide which tree goes under which.
    4. Loop over the nodes to start every node in a group of its own.
    5. Set parent[i] = i, so each node is the root of its own group.
    6. Set size[i] = 1, because a new int array holds zeros.
    7. Loop over edges with an enhanced for and an int[] named edge.
    8. Find rootA as find(parent, edge[0]). The helper is written at the end.
    9. Find rootB the same way for edge[1].
    10. If rootA == rootB, return false. The ends are already connected, so this edge closes a cycle.
    11. Check whether the group of rootA is the smaller one, size[rootA] < size[rootB].
    12. Save rootA in temp inside that if.
    13. Swap: copy rootB into rootA and temp into rootB. Now rootA is the root of the larger group.
    14. Merge by setting parent[rootB] to rootA.
    15. Add the sizes: size[rootA] += size[rootB]. The entry for rootB is never read again, because it is no longer a root.
    16. Return true after the loop: no edge closed a cycle.
    17. Write find, taking the parent array and a node x and returning the root.
    18. Loop while parent[x] != x, that is, while x is not a root.
    19. Halve the path: set parent[x] to parent[parent[x]].
    20. Move up: set x to parent[x], which is now the old grandparent.
    21. Return x after the loop.

    The solution in Java

    class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        int[] parent = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        for (int[] edge : edges) {
            int rootA = find(parent, edge[0]);
            int rootB = find(parent, edge[1]);
            if (rootA == rootB) {
                return false;
            }
            if (size[rootA] < size[rootB]) {
                int temp = rootA;
                rootA = rootB;
                rootB = temp;
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        return true;
    }

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

    The Java details worth a closer look:

    • Arrays are passed by reference. The variable parent holds a reference to the array, and find receives a copy of that reference, not a copy of the array. When find halves a path, validTree sees the change.
    • Primitives are passed by value. Assigning to x inside find changes only that method's own variable.
    • The swap needs temp. Writing rootA = rootB first would lose the old rootA.
    • int[][] is an array of arrays. edges.length is the number of edges, and each edge is an int[] of length 2, so edge[0] and edge[1] are its two ends.
    • A loop instead of recursion. A recursive find on a long chain could overflow the call stack. The loop in find uses constant stack, and with union by size the trees are shallow anyway.
    • Compound assignment. size[rootA] += size[rootB] adds in place, and the sizes never exceed n, so there is no overflow.

    Complexity

    The edge-count check is O(1). Setting up the arrays takes O(n). Each of the at most n - 1 edges costs two find calls and a constant amount of other work, and each find is O(α(n)) on average with path halving and union by size. The total is O((n + e) · α(n)), nearly O(n + e). The two arrays use O(n) extra space.

    Edge cases and common mistakes

    • Counting edges only. The edge count passes for n = 4 with a triangle plus an isolated node, which is not a tree. The cycle check is what rejects it.
    • Skipping the count. Without it, a graph with too few edges would return true when it is disconnected, because no edge closes a cycle. For n = 4 and [[0, 1], [2, 3]], union-find alone would accept it.
    • A single node. With n = 1 and no edges, the count 0 == n - 1 holds, no loop runs, and the answer is true. With n = 2 and no edges, the count fails and the answer is false.
    • Forgetting to set size to 1. With zeros, union by size can't tell the groups apart and the trees can grow deep.

    Testing

    These results come from running the solution, including a path of 100,000 nodes, which has the largest size the statement allows:

    nedgesResult
    5[[0, 1], [0, 2], [0, 3], [1, 4]]true
    5[[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]false
    4[[0, 1], [1, 2], [2, 0]]false
    1[]true
    2[]false
    4[[0, 1], [2, 3]]false
    3[[0, 1], [1, 2]]true
    100000the path [0, 1], [1, 2], …true
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free