AlgoMaster Logo

Redundant Connection

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We're given what was originally a tree with n nodes plus one extra edge. That extra edge creates exactly one cycle in the graph. The task is to find an edge we can remove to break the cycle and restore the tree structure. If multiple edges could work, we return the one that appears last in the input array.

A tree with n nodes has exactly n - 1 edges. The input has n edges (since n == edges.length), so exactly one edge is redundant. That redundant edge is the one that, when added, connects two nodes already linked through some existing path. It is the edge that completes a cycle.

The problem reduces to a single question: as we process edges one by one, which edge connects two nodes that are already in the same connected component?

Key Constraints:

  • n == edges.length with 3 <= n <= 1000 → A graph with n nodes and n edges has exactly one cycle, so exactly one edge is redundant. With n at most 1000, an O(n^2) DFS still finishes quickly, but Union Find brings it down to near-linear time.
  • 1 <= a_i < b_i <= n → Nodes are 1-indexed, edges list the smaller node first, and there are no self-loops, so we can size arrays as n + 1 and index directly by node label.

Approach 1: DFS Cycle Detection

Intuition

Process edges one at a time, building a graph as we go. Before adding each edge [u, v], run a DFS or BFS over the edges added so far to check whether u and v are already connected. If they are, adding this edge would close a cycle, so this edge is redundant.

Because we process edges in input order and the problem guarantees exactly one cycle, the first edge that joins two already-connected nodes is also the last such edge in the input. Returning it the moment we detect it satisfies the "occurs last in the input" requirement.

Algorithm

  1. Create an adjacency list for the graph (initially empty).
  2. Iterate through each edge [u, v] in order.
  3. Before adding the edge, run DFS from u to see if we can reach v using the edges already in the graph.
  4. If v is reachable from u, this edge creates a cycle. Return it.
  5. Otherwise, add the edge to the adjacency list and continue.

Example Walkthrough

1Process edge [1,2]: graph is empty, DFS from 1 can't reach 2
0
1
0
checking
1
checking
2
1
1
3
2
2
3
1/6

Code

Re-running a traversal for every edge is the cost here. The next approach maintains connectivity incrementally so each check is near-constant time.

Approach 2: Union Find (Optimal)

Intuition

Union Find (also called Disjoint Set Union) maintains a collection of disjoint sets and supports two operations: find (which set does an element belong to?) and union (merge two sets). With path compression and union by rank, both operations run in near-constant amortized time.

Process each edge in order. For each edge [u, v], check whether u and v already share a root. If they do, they are already connected and this edge is redundant. If they do not, call union to merge their components and move on.

Algorithm

  1. Initialize a Union Find structure with n+1 elements (nodes are 1-indexed).
  2. For each edge [u, v] in the input array:
    • Call find(u) and find(v) to get their root representatives.
    • If the roots are the same, u and v are already connected. Return this edge.
    • Otherwise, call union(u, v) to merge their components.
  3. Return an empty array (should never reach here given problem constraints).

Example Walkthrough

1Initialize: each node is its own parent
{ "nodes": [ 1, 2, 3, 4, 5 ], "parents": [ 0, 1, 2, 3, 4, 5 ] }
1/6

Code