Start learning free

LESSON 495 OF 572 · GRAPHS

Redundant Connection in C#: Union-Find, O(n * α(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

    C# · GRAPHS

    Redundant Connection in C#, explained

    Problem overview

    A tree is a connected graph with no cycle. You start with a tree of n nodes numbered 1 to n and add one extra edge between two nodes that were not joined before. The method FindRedundantConnection receives the resulting edges as an int[][] named edges, with n edges in total, and returns an edge that can be removed to leave a tree. If several edges would work, it returns the one that comes last in edges.

    For [[1,2],[1,3],[2,3]] the three edges form a triangle, and any one of them could go. The last is [2,3]. For [[1,2],[2,3],[3,4],[1,4],[1,5]] the cycle is 1-2-3-4-1, and the answer is [1,4]. The edge [1,5] comes later in the input, but it is not on the cycle: removing it would cut node 5 off.

    Approach: add the edges one at a time and look for the one that closes a cycle

    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 the cycle.

    It is also the right answer. The graph has exactly one cycle. Removing any edge on it leaves a tree, and removing an edge off it disconnects the graph. The cycle becomes complete when the last of its edges arrives, because all its other edges came earlier. So the first edge that closes a cycle is the cycle's last edge in the input, which is the answer even when other, unrelated edges come after it. For [[1,2],[2,3],[1,3],[3,4],[4,5]] the result is [1,3], not the final edge [4,5].

    The question "are these two nodes already connected?" is what union-find answers. It keeps the nodes in groups. Each node points to a parent, and a node that is its own parent is the root, which names its group. Two nodes are in the same group exactly when following parents from each leads to the same root. Merging two groups hangs one root under the other. Two tricks keep the trees shallow:

    • Union by size: the smaller group always goes under the larger one, so a node only moves deeper when its group at least doubles, and no path gets longer than about log2(n).
    • Path halving: while walking up in Find, every visited node is pointed at its grandparent, so later walks are shorter.

    Together they make each operation O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any size that fits in memory.

    Step by step

    1. Store n = edges.Length. A tree of n nodes has n - 1 edges, and the extra edge makes n, so the edge count is also the node count.
    2. Create parent and size as int arrays of length n + 1. Nodes are numbered from 1, so node i sits at index i and index 0 stays unused.
    3. Initialise them in a loop: parent[i] = i makes every node the root of its own group, and size[i] = 1 because a new int array holds zeros.
    4. Go over the edges in order with foreach.
    5. Find both roots: rootA for edge[0] and rootB for edge[1].
    6. Test for the cycle. If rootA == rootB, the ends are already connected through earlier edges, so return edge.
    7. Union by size. If size[rootA] < size[rootB], swap the two variables so that rootA is the larger group's root.
    8. Merge: set parent[rootB] = rootA and add size[rootB] to size[rootA].
    9. Return new int[0] after the loop. The input always has a redundant edge, so the loop returns first, but the method needs a return value on every path.
    10. Write Find. While parent[x] != x, set parent[x] = parent[parent[x]] (path halving) and move x = parent[x]. Return x.

    The solution in C#

    class Solution {
    public int[] FindRedundantConnection(int[][] edges) {
        int n = edges.Length;
        int[] parent = new int[n + 1];
        int[] size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        foreach (int[] edge in edges) {
            int rootA = Find(parent, edge[0]);
            int rootB = Find(parent, edge[1]);
            if (rootA == rootB) {
                return edge;
            }
            if (size[rootA] < size[rootB]) {
                (rootA, rootB) = (rootB, rootA);
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        return new int[0];
    }

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

    The C# details worth knowing:

    • Swapping with tuples. (rootA, rootB) = (rootB, rootA); builds a pair from the right side and then assigns it to the two variables on the left, so no temporary variable is needed.
    • Arrays are passed by reference. Find receives the same array as the caller, so its change to parent is visible in FindRedundantConnection. The parameter x is a plain int copy, and changing it inside Find doesn't affect the caller's variable.
    • The result is the input's own array. return edge; hands back one of the arrays inside edges, not a copy. Modifying the returned array would modify the input as well.
    • A loop, not recursion. Find is iterative, so a long chain of parents can't overflow the call stack.
    • Initial values. New int arrays are filled with 0, so size needs the explicit 1.

    Complexity

    Time: O(n * α(n)), which is nearly O(n). Each of the n edges costs two Find calls and a constant amount of merging, and with union by size and path halving each Find is O(α(n)) amortized.

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

    Edge cases and common mistakes

    • Returning the last edge of the input. It is right for [[1,2],[1,3],[2,3]] but wrong for [[1,2],[2,3],[3,4],[1,4],[1,5]], where it gives [1,5] and the answer is [1,4].
    • The cycle's last edge isn't at the end. [[1,2],[2,3],[1,3],[3,4],[4,5]] returns [1,3].
    • Edges that join separate groups. In [[1,2],[3,4],[2,3],[4,5],[1,5]] the edge [2,3] has both nodes seen already, but in different groups, so it merges them. Only [1,5] finds the two ends in the same group, and it is the answer.
    • Arrays of size n instead of n + 1. Node n would be at index n, outside the array, and Find throws an IndexOutOfRangeException.
    • Comparing nodes instead of roots. edge[0] == edge[1] never detects a cycle. Compare the results of Find.
    • Forgetting the merge. Without the assignment to parent[rootB], the groups never grow and the loop ends without finding a cycle, so the method returns the empty array.

    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],[4,5]] gives [1,3].
    • [[1,2],[1,3],[1,4],[1,5],[4,5]] gives [4,5].
    • A chain of 1000 nodes, [1,2] to [999,1000], followed by [1,1000], gives [1,1000].
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free