MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Redundant Connection

1 approach, code in all languages

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 unlock the solution

See 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

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI