MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Redundant Connection

1 approach, code in every language

You start with a tree that has n nodes labeled from 1 to n, meaning it is connected and contains no cycles. Someone then adds exactly one extra edge between two distinct nodes that were already in the tree, creating a graph with n edges and exactly one cycle.

You are given the resulting edges as a list, where edges[i] = [a, b] indicates an undirected edge between nodes a and b. Return an edge that can be removed so the remaining graph is again a tree of n nodes.

If several answers exist, return the edge that appears last in the input.

Example 1

Input: edges = [[1,2],[1,3],[2,3]]

Output: [2,3]

Edges [1,2] and [1,3] already connect all three nodes; adding [2,3] closes a cycle, so removing it restores a tree.

Example 2

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output: [1,4]

By the time [1,4] is processed, nodes 1 and 4 are already connected through 1-2-3-4, so [1,4] is the redundant edge.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= a_i < b_i <= edges.length
a_i != b_i
There are no repeated edges.
The given graph is connected.

Union-Find (Cycle Detection)

Add edges one by one; the first edge whose endpoints already share a root is the redundant one.

Loading animation…

Intuition

The graph is a tree with one extra edge, so it holds exactly one cycle. Processing edges from left to right with Union-Find, a normal edge always joins two previously separate groups. The offending edge is the first one whose two endpoints already belong to the same set, because linking them again is what closes the cycle. Since we scan in input order, this edge is simultaneously the last edge in the input that completes the cycle, which is exactly what the problem requests.

Algorithm walkthrough

1Create a parent array covering nodes 1..n, each initially its own root.
2Iterate through the edges in the order they are given.
3For an edge (a, b), compute the roots of a and b.
4If the two roots are equal, a and b are already connected, so this edge closes the cycle and is the answer.
5Otherwise union the two groups and continue to the next edge.

Implementation

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return [a, b]
            parent[ra] = rb
        return []

Time

O(n * α(n))

Space

O(n)

Each of the n edges triggers a constant number of near-constant amortized union/find operations, where α is the inverse Ackermann function.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Surplus Irrigation Link is our own problem on the technique behind Redundant Connection: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free