684. Redundant Connection - Detailed Explanation

Problem Statement

You’re given a list of undirected edges edges where each edge connects two nodes in a graph labeled from 1 to n. The graph started as a tree on n nodes (i.e. connected and acyclic), and then one extra edge was added, creating exactly one cycle. Return the extra edge that, if removed, would restore the tree property. If there are multiple candidates, return the one that appears last in the input.

Examples

Example 1

Input   edges = [[1,2],[1,3],[2,3]]
Output  [2,3]
Explanation  Adding [2,3] creates a cycle 1–2–3–1. Removing it restores a tree.

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; the last edge in the input among these is [1,4].

Constraints

3 ≤ edges.length = n ≤ 1000
edges[i].length == 2
1 ≤ edges[i][j] ≤ n
No repeated edges
Exactly one extra edge creates a single cycle

Hints

How can you detect the moment you introduce a cycle when adding edges one by one?
Which data structure supports “merge two sets” and “find representative” efficiently?
When you find that both endpoints of an edge are already in the same set, that edge is the redundant one.

Approach – Union‑Find (Disjoint Set Union)

We’ll process edges in input order, maintaining a DSU over the nodes. For each edge (u,v), if u and v are already connected (same root), then (u,v) is the redundant edge; otherwise we union them.

Steps

Initialize a DSU for nodes 1 through n.
Iterate over edges in order:
- Let (u,v) be the current edge.
- If find(u) == find(v), return [u,v].
- Else union(u,v).
(By problem guaranteeing one extra edge, we always return inside the loop.)

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time: O(n α(n)) ≈ O(n), where α is the inverse Ackermann function (very slow‑growing).
Space: O(n) for DSU arrays.

Step‑by‑Step Walkthrough

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

Union(1,2) → merges sets {1} and {2}.
Union(1,3) → merges {1,2} with {3}.
Union(2,3) → find(2)==find(3) → cycle detected → return [2,3].

Common Mistakes

Forgetting path compression or union by rank may still pass for n≤1000 but degrade performance.
Using 0‑based DSU on 1‑based node labels without shifting indices.
Returning the first cycle edge when the problem asks for the last in input order (this solution inherently does that by scanning in order).

Edge Cases

The cycle is formed by the very first extra edge (smallest index).
The redundant connection involves the highest‑numbered node.
Graph with n=3 and edges exactly forming one triangle.

Alternative Variations

If you needed all edges in the cycle, you could build the spanning tree then traverse to extract the unique cycle.
For a directed graph variant, use DFS with recursion stack to detect the back edge.