Redundant Connection

Redundant Connection medium

Description

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The resulting graph has exactly one cycle.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input edges.

Examples

> Case 1:
    edges = [[1,2],[1,3],[2,3]]
    Output: [2, 3]
 
> Case 2:
    edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
    Output: [1, 4]

Constraints

n == edges.length
3 <= n <= 1000
1 <= a_i, b_i <= n
a_i != b_i
No repeated edges.

State design

Process edges in order. For each (u, v):

If find(u) == find(v) → adding this edge would create a cycle → it’s the redundant one. Return it.
Otherwise, union(u, v).

The “if multiple answers, return the last” clause is automatically handled — we return the first cycle-closing edge we encounter while scanning left-to-right, which is equivalent to “the last edge causing the cycle in the original input order” since by the time we see it, the cycle didn’t exist yet.

The vertices are 1-indexed; size the DSU to n + 1.

Code

Analysis

Time: O(n · α(n)).
Space: O(n).

Why this isn’t more general. This problem guarantees exactly one extra edge producing exactly one cycle. Real “find the edge to remove to break a cycle” is harder in a directed graph with multiple cycles — see Redundant Connection II (LeetCode 685) for the directed variant, which adds a parent-check twist.

Same skin

Redundant Connection II (directed) — directed version; mix of cycle and 2-parent cases.
Graph Valid Tree — same DSU shape, but checks the full graph.
Critical Connections in a Network — bridges via Tarjan’s, conceptually opposite (find an edge whose removal disconnects).

Graph Valid Tree Satisfiability of Equality Equations