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 graph is represented as an array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree. If there are multiple answers, return the last edge that appears in the input.

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
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
There are no repeated edges.
The given graph is connected.

State design / Intuition

Process edges one by one. Use Union-Find to track connected components. The first edge where both endpoints are already in the same component is the redundant one — adding it would create the cycle.

Because the problem guarantees exactly one extra edge and asks for the last one in the input if there are multiple options, the first cycle-forming edge encountered when processing in order is our answer.

Code

This is also solvable with DFS: find a cycle in the graph, then return the last edge in the cycle that appears in the input. Union-Find is faster (O(n α(n)) vs O(n²)) and simpler to implement correctly.

Analysis

Time: O(n α(n)) ≈ O(n) — n Union-Find operations.
Space: O(n) — parent and rank arrays.

Same skin

Redundant Connection II (LC 685) — directed graph version; need to handle multiple cases (incoming degree 2, or a cycle without a double-in-degree node).
Number of Connected Components — same union-find, count components.
Graph Valid Tree (LC 261) — same check: n nodes, n−1 edges, no cycles = valid tree.
Accounts Merge — union-find on email strings; same component = same person.

Min Cost to Connect All Points Network Connected