Start learning free

LESSON 496 OF 573 · GRAPHS

Redundant Connection in Scala: Union-Find in Near O(n)

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

A tree is an undirected graph that is connected (you can get from any node to any other by following edges) and has no cycle. Put another way, there is exactly one path between any two nodes.

You start with a tree of n nodes, numbered from 1 to n, and one extra edge is added to it. The extra edge joins two different nodes that were not joined by an edge before. The graph you get is given as an array edges of length n, where edges[i] = [ai, bi] means that there is an edge between nodes ai and bi.

Return an edge that can be removed so that the other n - 1 edges form a tree of all n nodes. If several edges work, return the one that comes last in edges.

 

Example 1:

Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: The three edges form the cycle 1 - 2 - 3 - 1:
      1
     / \
    2 - 3
Removing any one of them leaves a tree. [2, 3] is the one that comes last.

Example 2:

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Explanation: The cycle is 1 - 2 - 3 - 4 - 1:
    5 - 1 - 2
        |   |
        4 - 3
[1, 5] comes after [1, 4] in the input, but removing it would cut node 5 off from the others.
Of the four edges on the cycle, [1, 4] comes last.

Example 3:

Input: edges = [[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]]
Output: [1, 5]
Explanation: When [2, 3] comes, nodes 2 and 3 have both been seen already, but in two
separate groups, {1, 2} and {3, 4}: the edge joins them. All five edges form the cycle
1 - 2 - 3 - 4 - 5 - 1, and [1, 5] comes last.

 

Constraints:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= n
  • There are no repeated edges.
  • The graph is connected.

Note:

Your algorithm should run in O(n·α(n)) time, nearly O(n), and use O(n) extra space.

Trying each edge from the last one back, removing it and checking with a DFS whether the rest is still connected, costs O(n2). The tutorial adds the edges one by one, in the order they are given, with union-find, as in Graph Valid Tree: an edge whose two nodes are already in the same group closes a cycle. The graph has exactly one cycle, and removing any of its edges leaves a tree, while removing an edge that is not on it cuts the tree in two. The cycle closes when the last of its edges comes, because all its other edges came before, so the first edge that closes a cycle is the answer. With path halving and union by size, each step costs O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any n a computer can hold.

STEP 1 OF 19
    Ctrl + Enter to check

    SCALA · GRAPHS

    Redundant Connection in Scala, explained

    Problem overview

    A tree is a connected graph with no cycle. You get a tree of n nodes, numbered from 1 to n, with one extra edge added between two nodes that were not joined before. The graph is given as edges, an Array[Array[Int]] of length n where each element is a pair [a, b]. The method findRedundantConnection returns an edge that can be removed so that the other n - 1 edges form a tree. When several edges would work, it returns the one that comes last in edges.

    In [[1,2],[2,3],[3,4],[1,4],[1,5]] the cycle is 1 - 2 - 3 - 4 - 1. Removing any of its four edges leaves a tree, and [1,4] comes last among them. The edge [1,5] comes later in the input, but it is not on the cycle: removing it would cut node 5 off. The answer is [1,4].

    Approach: add the edges one by one with union-find

    Trying every edge from the last one back, removing it and checking with a depth-first search whether the rest is still connected, costs O(n^2). A better way is to build the graph edge by edge, in the given order, and watch for the first edge whose two ends are already connected.

    That edge closes a cycle. The graph has exactly one cycle, and all the other edges of the cycle came before the edge that closes it, so it is the cycle's last edge in the input. That is the answer, even when edges that are not on the cycle come after it.

    Union-find answers "are these two nodes already connected?" quickly. It keeps each group of connected nodes as a tree of parent pointers. The root, the only node that is its own parent, names the group. Two nodes are in the same group exactly when they lead to the same root. Two refinements keep the trees shallow: union by size attaches the smaller tree under the larger one, and path halving shortens paths while walking up. Together they make each operation nearly constant time, O(alpha(n)) amortized, where alpha is the inverse Ackermann function.

    Step by step

    1. Store n as edges.length. A tree of n nodes has n - 1 edges and the extra one makes n, so the edge count is also the node count.
    2. Create parent with Array.tabulate(n + 1)(i => i): every node starts as its own root. Nodes are numbered from 1, so the arrays have n + 1 entries and index 0 is unused.
    3. Create size with Array.fill(n + 1)(1). For a root r, size(r) is the number of nodes in its group.
    4. Loop over the edges in the given order. The order decides which edge of the cycle comes back.
    5. Find the root of edge(0) with find, stored in a var called rootA, because it may be swapped later.
    6. Find the root of edge(1) the same way, as rootB.
    7. Compare the roots. If rootA == rootB, the two ends are already connected through earlier edges, so this edge closes the cycle: return edge.
    8. Union by size. If size(rootA) < size(rootB), swap the two roots, so that rootA is the root of the larger group.
    9. Save rootA in temp before overwriting it.
    10. Copy and restore: rootA = rootB, then rootB = temp.
    11. Merge: parent(rootB) = rootA hangs the smaller tree under the larger one.
    12. Update the size: size(rootA) += size(rootB).
    13. Return an empty array after the loop, Array[Int](). The input always has an extra edge, so the loop returns first; the line exists because the method must produce a value on every path.
    14. Write find, taking parent and node and returning an Int.
    15. Copy node into var x, because parameters can't be reassigned.
    16. Loop while parent(x) != x: a node that is not its own parent is not a root yet.
    17. Halve the path: parent(x) = parent(parent(x)) makes x point to its grandparent.
    18. Move up: x = parent(x), so each turn climbs two levels.
    19. Return x, the root.

    The solution in Scala

    class Solution {
    def findRedundantConnection(edges: Array[Array[Int]]): Array[Int] = {
        val n = edges.length
        val parent = Array.tabulate(n + 1)(i => i)
        val size = Array.fill(n + 1)(1)
        for (edge <- edges) {
            var rootA = find(parent, edge(0))
            var rootB = find(parent, edge(1))
            if (rootA == rootB) {
                return edge
            }
            if (size(rootA) < size(rootB)) {
                val temp = rootA
                rootA = rootB
                rootB = temp
            }
            parent(rootB) = rootA
            size(rootA) += size(rootB)
        }
        Array[Int]()
    }

    def find(parent: Array[Int], node: Int): Int = {
        var x = node
        while (parent(x) != x) {
            parent(x) = parent(parent(x))
            x = parent(x)
        }
        x
    }
}

    Scala details worth a look:

    • Arrays are shared, not copied. find receives the same parent array, so the path halving it does is visible to the caller.
    • val versus var. rootA and rootB are vars because they are swapped. parent and size are vals: the reference never changes, although the array's contents do.
    • The swap needs a temporary. Writing rootA = rootB first would lose the old value of rootA.
    • size(rootA) += size(rootB) is shorthand for reading, adding and storing back into the array element.
    • return edge inside the for. A for over an array is a call to foreach with a lambda, so this return leaves the whole method from inside that lambda. Scala 3.5 accepts it and the method works, but the compiler prints a warning: "Non local returns are no longer supported; use boundary and boundary.break in scala.util instead".
    • The last expression is the value. x alone on the last line of find is what it returns.

    A trace

    For edges = [[1,2],[3,4],[2,3],[4,5],[1,5]], this is the state after each edge. The lists show parent and size for the nodes 1 to 5:

    EdgeRootsparentsize
    [1,2]1 and 21, 1, 3, 4, 52, 1, 1, 1, 1
    [3,4]3 and 41, 1, 3, 3, 52, 1, 2, 1, 1
    [2,3]1 and 31, 1, 1, 3, 54, 1, 2, 1, 1
    [4,5]1 and 51, 1, 1, 1, 15, 1, 2, 1, 1
    [1,5]1 and 1same root: return [1,5]

    When [2,3] arrives, nodes 2 and 3 are both known, but they are in different groups, the one with root 1 and the one with root 3, so the edge joins them. The last edge finds both nodes under root 1.

    Complexity

    Time: O(n * alpha(n)), nearly O(n). Each of the n edges costs two calls to find, each O(alpha(n)) amortized, plus constant work for the union.

    Space: O(n) for the parent and size arrays.

    Edge cases and common mistakes

    • The cycle is closed before the end. For [[1,2],[2,3],[1,3],[3,4]] the method returns [1,3]. The edge [3,4] comes after it, but it is not on the cycle.
    • Returning the last edge of the input. That is wrong whenever the last edge is not on the cycle, as in the previous case or in the example with node 5.
    • Index 0. With nodes numbered from 1, arrays of size n would be too short for node n. That is why they have n + 1 entries.
    • Comparing the nodes instead of the roots. Two nodes in the same group are not equal; the test must compare the results of find.
    • Skipping the swap. Attaching the larger tree under the smaller one still gives correct answers, but the trees can grow deep and lose the near-constant cost.

    Testing

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