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

1. How can you detect the moment you introduce a cycle when adding edges one by one?
2. Which data structure supports “merge two sets” and “find representative” efficiently?
3. 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

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

Code (Python)

Java Code