LeetCode #684 Medium

Redundant Connection

A tree of n nodes had one extra edge added, creating exactly one cycle. Find the redundant edge that can be removed.

graphunion-find

Open on LeetCode ↗

02

Intuition

💡

The trap is trying to find the cycle first and then picking an edge out of it. Union-Find answers this in a single pass: process the edges in the given order, and the first edge whose two endpoints already share a root is exactly the edge that closes a cycle -- everything before it built a valid forest. Because a valid tree on n nodes has exactly n-1 edges, and this input has n, there is exactly one such moment, and returning immediately there gives the LAST such edge in input order, which is precisely what the problem asks for.

03

Approach

1

Union-Find, one pass over edges

Maintain a parent array. For each edge [u, v] in order, find the roots of u and v.

2

Same root means redundant

If find(u) == find(v), the two nodes were already connected before this edge -- adding it creates a cycle. Return this edge immediately; no need to search for the cycle explicitly.

3

Different roots means union and continue

Otherwise union the two sets (attach one root under the other) and move to the next edge -- this edge is a legitimate tree edge.

04

Solution & live demo

python

▶1class Solution:
▶2    def findRedundantConnection(self, edges):
▶3        n = len(edges)
▶4        parent = list(range(n + 1))
▶5        def find(x):
▶6            while parent[x] != x:
▶7                parent[x] = parent[parent[x]]
▶8                x = parent[x]
▶9            return x
▶10        for u, v in edges:
▶11            ru, rv = find(u), find(v)
▶12            if ru == rv:
▶13                return [u, v]
▶14            parent[ru] = rv
▶15        return []

05

Edge cases

Cycle formed by the very first redundant edge encountered

Union-Find catches it the instant both endpoints share a root -- no lookahead needed.

Multiple edges could close different cycles

Problem guarantees exactly one extra edge, so only one edge ever finds matching roots.

Self-loop edge [a, a]

find(a) == find(a) trivially -- would be reported as redundant immediately.

Answer must be the LAST qualifying edge

Processing in input order and returning at the first same-root hit naturally gives the last edge in the original list that closes the cycle.

06

Complexity

Time

O(n * alpha(n))

Space

O(n)

Near-constant per operation with path compression and union by attaching roots.