Start learning free

LESSON 475 OF 541 · GRAPHS

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

    SWIFT · GRAPHS

    Graph Valid Tree in Swift, 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 the edges make the graph a tree: connected, so you can get from any node to any other, and with 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 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] the answer is false, because the edges 1-2, 2-3 and 1-3 form a cycle. For n = 4 and edges = [[0, 1], [1, 2], [2, 0]] the answer is false too: the count of 3 edges is right for 4 nodes, but 0, 1 and 2 form a cycle and node 3 has no edge at all.

    The statement asks for nearly O(n + e) time (precisely O((n + e)·α(n))) and O(n) extra space, where e is the number of edges.

    Approach: count the edges, then look for a cycle

    A tree with n nodes has exactly n - 1 edges. With fewer, some node is cut off. With more, some edge closes a cycle. So if edges.count != n - 1, the answer is false immediately.

    With exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle. Counting alone isn't enough, as the third example shows, so the solution checks each edge with union-find. It keeps the nodes in groups, each stored as a small tree: every node has a parent, and the root, the one node that is its own parent, names the group. At the start every node is alone.

    For each edge, find the roots of both ends. If they are the same root, the two nodes were already connected, so this edge adds a second path between them: a cycle, and the answer is false. Otherwise merge the two groups. If no edge closes a cycle, every one of the n - 1 edges merged two groups, so the n single nodes became one group, and the graph is a tree.

    Two tricks keep the walks to a root short. Union by size hangs the smaller group under the larger one's root. Path halving makes every node passed during a walk point to its grandparent. Together they make each step cost O(α(n)) on average, where α is the inverse Ackermann function, below 5 for any size a computer can hold.

    A depth-first or breadth-first search from node 0 that checks every node is reached also works once the edge count is right. With up to 100,000 nodes, use a queue or your own stack rather than recursion, since a recursive search down a path that long can overflow the call stack.

    The state after each edge of the first example (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]

    At the end every node leads to root 0, and the group has size 5.

    Step by step

    1. Check the edge count. If edges.count is not n - 1, return false.
    2. Create parent with Array(0..<n), so parent[i] is i: every node is the root of a group of one. It is a var because find changes it.
    3. Create size as n ones. size[r] counts the nodes in the group whose root is r.
    4. Loop over edges. Each edge either merges two groups or closes a cycle.
    5. Find the root of edge[0] with find(&parent, edge[0]) into rootA. The & is required because find takes the array as an inout parameter. It is a var because the size step may swap it.
    6. Find the root of edge[1] into rootB.
    7. If the roots are equal, return false. The two ends are already connected, so the edge closes a cycle.
    8. Make rootA the root of the larger group. If size[rootA] < size[rootB], swap them with one tuple assignment. A node only moves one level deeper when its group at least doubles, so no path to a root grows beyond about log2(n) steps.
    9. Merge: set parent[rootB] to rootA.
    10. Update the size: add size[rootB] to size[rootA].
    11. Return true after the loop, since no edge closed a cycle.
    12. Write find below validTree, as a method taking _ parent: inout [Int] and _ node: Int and returning an Int.
    13. Copy node into a var x, since parameters are constants and x walks up the tree.
    14. Loop while parent[x] != x. The root is the only node that is its own parent. The loop needs no call stack, however long the walk.
    15. Halve the path: set parent[x] to parent[parent[x]].
    16. Climb: set x to parent[x], the grandparent it now points to.
    17. Return x, the root.

    The solution in Swift

    class Solution {
    func validTree(_ n: Int, _ edges: [[Int]]) -> Bool {
        if edges.count != n - 1 {
            return false
        }
        var parent = Array(0..<n)
        var size = [Int](repeating: 1, count: n)
        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] {
                (rootA, rootB) = (rootB, rootA)
            }
            parent[rootB] = rootA
            size[rootA] += size[rootB]
        }
        return true
    }

    func find(_ parent: inout [Int], _ node: Int) -> Int {
        var x = node
        while parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
}

    The Swift details worth a closer look:

    • inout and &. Arrays are value types, so a function normally works on a copy. An inout parameter lets find change the caller's array, and the caller must pass it with &. Leaving it out is a compile error: passing value of type '[Int]' to an inout parameter requires explicit '&'.
    • Array(0..<n). It turns the range into the array [0, 1, ..., n - 1], which is exactly the starting parent table.
    • Tuple swap. (rootA, rootB) = (rootB, rootA) builds a pair from the right side, then unpacks it into the left side, so the swap needs no temporary variable.
    • var for the roots. rootA and rootB are reassigned by the swap, so they can't be let.
    • Parameters are constants. That is why find copies node into var x.

    Complexity

    Time: O((n + e)·α(n)), nearly O(n + e). The count check is constant. Building the arrays is O(n). Each of the at most n - 1 edges (after the count check) does two find calls and a merge, each costing O(α(n)) on average.

    Space: O(n). The parent and size arrays hold n integers each.

    Edge cases and common mistakes

    • Counting edges only. n = 4 with [[0, 1], [1, 2], [2, 0]] has the right count but is not a tree. The cycle check is needed.
    • A single node. n = 1 with no edges returns true: zero edges is n - 1, and the loop does nothing.
    • No edges, several nodes. n = 2 with [] returns false, because the count is 0, not 1.
    • Edge direction. The edges are undirected, so [[1, 0]] with n = 2 returns true just like [[0, 1]].
    • Order of the edges. [[0, 1], [2, 3], [1, 2]] with n = 4 returns true: the groups {0, 1} and {2, 3} are merged by the last edge.
    • Too few edges. [[0, 1], [1, 2]] with n = 4 returns false, because the count is 2 instead of 3.
    • Forgetting &. The call won't compile without it, as shown above.

    Testing

    • n = 5, [[0, 1], [0, 2], [0, 3], [1, 4]] gives true.
    • n = 5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] gives false.
    • n = 4, [[0, 1], [1, 2], [2, 0]] gives false.
    • n = 1, [] gives true.
    • n = 2, [] gives false.
    • n = 2, [[1, 0]] gives true.
    • n = 4, [[0, 1], [2, 3], [1, 2]] gives true.
    • n = 4, [[0, 1], [1, 2]] gives false.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free