Start learning free

LESSON 474 OF 540 · GRAPHS

Graph Valid Tree in Kotlin: 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 19
    Ctrl + Enter to check

    KOTLIN · GRAPHS

    Graph Valid Tree in Kotlin, explained

    Problem overview

    You get n nodes numbered 0 to n - 1 and an array edges of undirected edges, each an IntArray with two node numbers. The function validTree returns true when the graph is a tree. A tree is connected (every node can reach every other) and has no cycle, which is the same as saying that exactly one path joins any two nodes.

    With n = 5 and edges [0, 1], [0, 2], [0, 3], [1, 4], every node hangs off node 0 and no edge closes a loop: the answer is true. With [0, 1], [1, 2], [2, 3], [1, 3], [1, 4] the edges 1-2, 2-3 and 1-3 form a cycle: false.

    Approach

    Two facts reduce the problem. A tree with n nodes has exactly n - 1 edges. And with exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle: if no edge ever joins two nodes that are already connected, every edge merges two separate groups, and the n single nodes end up as one group.

    The count alone is not enough. With n = 4 and edges [0, 1], [1, 2], [2, 0] there are 3 edges, the right number, but they form a triangle and node 3 has no edge at all. The result is false, and it is the cycle check that finds it.

    To detect cycles, use union-find (also called disjoint sets). Each group of connected nodes is stored as a tree of parent pointers, and the root, the one node that is its own parent, names the group. Two nodes are in the same group exactly when they lead to the same root. For each edge:

    • if both ends already have the same root, the edge closes a cycle, so return false;
    • otherwise merge the two groups by hanging one root under the other.

    Two refinements keep the trees shallow. Union by size hangs the smaller tree under the larger one, so a node only gets deeper when its group at least doubles. Path halving makes each node passed during a search skip one level. Together they make each operation cost O(α(n)) on average, where α is the inverse Ackermann function, below 5 for any size a computer can hold. A DFS or BFS from node 0 also works, but a recursive DFS down a path of 100,000 nodes can run out of call stack.

    The state after each edge of the first example, from a real run (parent and size by node number):

    edge 0-1 parent=0,0,2,3,4 size=2,1,1,1,1
edge 0-2 parent=0,0,0,3,4 size=3,1,1,1,1
edge 0-3 parent=0,0,0,0,4 size=4,1,1,1,1
edge 1-4 parent=0,0,0,0,0 size=5,1,1,1,1

    Every edge merges two groups, and at the end all five nodes share the root 0.

    Step by step

    1. Check the edge count. If edges.size != n - 1, return false. Fewer edges leave some node cut off; more edges force a cycle.
    2. Create the parents. IntArray(n) { it } gives each node itself as its parent. The block runs once per index, and it is that index. Every node starts as the root of a group of one.
    3. Create the sizes. IntArray(n) { 1 }. Only the roots' entries are kept up to date.
    4. Loop over the edges. for (edge in edges); each edge merges two groups or closes a cycle.
    5. Find the first root. var rootA = find(parent, edge[0]). It is a var because the size comparison may swap it.
    6. Find the second root. var rootB = find(parent, edge[1]).
    7. Detect the cycle. If rootA == rootB, the ends are already connected, this edge adds a second path between them, and the function returns false.
    8. Choose the larger group. If size[rootA] < size[rootB], swap the two roots with a temporary variable, so that rootA always ends up as the root of the larger group.
    9. Merge. parent[rootB] = rootA hangs the smaller tree under the larger.
    10. Update the size. size[rootA] += size[rootB]. The size of rootB is never read again, because it is no longer a root.
    11. Return true. After the loop, no edge closed a cycle. All n - 1 edges merged two groups, so the graph is connected.
    12. Write find. It copies node into var x, then loops while parent[x] != x: set parent[x] = parent[parent[x]] (path halving), then x = parent[x]. It returns x, the root.

    The solution in Kotlin

    class Solution {
    fun validTree(n: Int, edges: Array<IntArray>): Boolean {
        if (edges.size != n - 1) {
            return false
        }
        val parent = IntArray(n) { it }
        val size = IntArray(n) { 1 }
        for (edge in edges) {
            var rootA = find(parent, edge[0])
            var rootB = find(parent, edge[1])
            if (rootA == rootB) {
                return false
            }
            if (size[rootA] < size[rootB]) {
                val temp = rootA
                rootA = rootB
                rootB = temp
            }
            parent[rootB] = rootA
            size[rootA] += size[rootB]
        }
        return true
    }
    fun find(parent: IntArray, node: Int): Int {
        var x = node
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
}

    Kotlin details worth knowing:

    • Arrays are passed by reference. find receives the same parent array, not a copy, so its path halving changes the array that validTree uses. That is intended.
    • Parameters are read-only. find can't change node, so it walks with its own var x.
    • val and var. parent and size are val because the arrays themselves are never replaced, although their contents change. rootA and rootB are var because they are reassigned in the swap.
    • IntArray(n) { it } builds the identity array without a loop of your own.
    • No recursion. find uses a while loop, so a long chain can't overflow the call stack.

    Complexity

    Each of the e edges costs two find calls and a few assignments. With union by size and path halving, a call takes O(α(n)) on average, so the total is O((n + e) · α(n)), nearly O(n + e). The count check at the start means the loop never runs on more than n - 1 edges. The two arrays hold n entries each, so the extra space is O(n).

    Edge cases and common mistakes

    • Counting edges only. n = 4 with the triangle [0, 1], [1, 2], [2, 0] has the right count and is not a tree. The union-find loop returns false on the third edge.
    • Skipping the count check. Without it, a graph with too few edges (for example n = 4 and a single edge) would pass the cycle loop, since there is no cycle, even though it isn't connected.
    • Single node. n = 1 with no edges is a tree: edges.size is 0, which equals n - 1, and the loop doesn't run. The result is true. n = 2 with no edges returns false.
    • Edge direction. Edges are undirected, so [1, 0] and [0, 1] behave the same.
    • Forgetting to compare roots. Comparing edge[0] with edge[1] directly says nothing about connectivity; compare their roots.
    • Deep recursion. A recursive find on a long chain can overflow the stack. The loop version has no such limit.

    Testing

    Results from running the solution:

    • n = 5, [[0,1],[0,2],[0,3],[1,4]]: true
    • n = 5, [[0,1],[1,2],[2,3],[1,3],[1,4]]: false
    • n = 4, [[0,1],[1,2],[2,0]]: false
    • n = 1, no edges: true
    • n = 2, no edges: false
    • n = 2, [[1,0]]: true
    • n = 4, [[0,1],[2,3]]: false
    • A chain of 100,000 nodes, [[0,1],[1,2],…]: true
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free