684. Redundant Connection

684

MediumUnion-Find / Disjoint Set UnionUnion-Find (Disjoint Set Union)Cycle detection while building

Redundant Connection

You start with a tree of n nodes labeled 1..n (n-1 edges, connected, acyclic), then one extra edge is added, creating exactly one cycle. Given the list of edges in the order they were added, return the one edge that can be removed so the graph is a tree again. If several answers exist, return the edge that appears last in the input.

Open official problem prompt ↗

In plain English

Find the single edge whose removal turns the given one-cycle graph back into a spanning tree, preferring the later edge when there is a tie.

Picture it like this

Imagine merging friend groups: each edge says two people are friends, so you merge their groups. The edge that connects two people already in the same group tells you nothing new; that is the redundant introduction.

Example

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Why: Nodes 1, 2, 3 are already connected by [1,2] and [1,3]; adding [2,3] closes a cycle, so [2,3] is the redundant edge.

Constraints

n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biThere are no repeated edgesThe given graph is connected and has exactly one cycle

Pattern lesson

See the pattern, then code

Cycle detection while building

↗

Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Process edges in order and union their endpoints. The first (and here only) edge whose two endpoints already share a root does not connect anything new, so it is the redundant edge that closes the cycle.

New words, made simpleKnow these before the algorithm

Disjoint set: A collection of groups where every element belongs to exactly one group.
Root / representative: A designated element that identifies a group; two elements are connected iff they share a root.
Path compression: Flattening the parent chain during find so future lookups are near constant time.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Remove-and-check DFS

Works but re-runs a traversal per candidate edge, which is wasteful.

Try removing each edge from last to first and test if the remaining graph is a connected tree via DFS.

Time O(n^2)Space O(n)

Best choiceUnion-Find in insertion order

Single pass, near-linear, and naturally returns the last-added cycle edge.

Union endpoints as edges arrive; the first edge whose endpoints already share a root is the answer.

Time O(n α(n))Space O(n)

The rule we keep true

Invariant

After processing a prefix of edges, two nodes share a root if and only if they are connected using only the edges seen so far.

Why this is correct

Reasoning

The graph is a tree plus one edge, so exactly one edge closes a cycle. Scanning in order, every tree edge connects two previously separate components and is unioned; the unique cycle edge is the first time both endpoints already share a root, and because it is the only such edge it is also the last one that could be removed.

The algorithm in three movesSay these aloud before coding

1Initialize a parent array so every node is its own root

after [1,2]: {1->1, 2->1}

2For each edge (a, b), find the roots of a and b

after [1,3]: {1->1, 2->1, 3->1}

3If the roots are equal, this edge creates a cycle, return it

[2,3]: find(2)=find(3)=1 -> cycle, return [2,3]

4Otherwise union the two roots and continue

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1-20

1-31

2-32

1 · Reada=1, b=2

2 · AskSame root?

3 · Update stateparent={1:1,2:2,3:3}

4 · Resultfind(1)=1, find(2)=2 differ; union -> 2 points to 1

Key takeaway

Edges added left to right; the third edge finds both endpoints already in the same set.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Parent array
Indices 0..n; node i starts as its own root (index 0 is unused since labels start at 1).
2
Lines 5-9find with path compression
Walks to the root while pointing each node at its grandparent to keep chains short.
3
Lines 11-15Scan and union
For each edge, equal roots mean a cycle so return immediately; otherwise merge the two sets.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

The redundant edge connects two of the very first nodes (still detected the moment both roots match)
A node label equals n so the parent array must have size n+1
Self-referential input is impossible here because ai != bi is guaranteed

Common beginner mistakes

Sizing the parent array to n instead of n+1 and indexing out of range because labels are 1-based
Returning the first cycle edge found by node value order instead of respecting input order (input order already gives the correct last edge)
Forgetting to actually union non-cycle edges, which breaks connectivity tracking

Check your understanding

Why is the first edge whose endpoints already share a root guaranteed to be the answer LeetCode wants (the last removable edge)?

Redundant Connection

Redundant Connection

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Union-Find / Disjoint Set Union