Redundant Connection

1. Define the problem

You are given a graph that started as a tree with n nodes labeled 1 to n, with one additional edge added. 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. Process edges in order, and before unioning two nodes call find on both. The first edge whose endpoints already share a root is the redundant one.

Constraints

n == edges.length
3 ≤ n ≤ 1000
edges_i.length == 2
1 ≤ ai < bi ≤ edges.length
ai != bi

Example

Inputedges = [[1,2],[1,3],[2,3]]

Output[2,3]

Explanation Edges [1,2] and [1,3] build the tree. Edge [2,3] closes a cycle back to node 1.

2. Visualize the solution

Union edges in order, stop at the first repeat root

node 1parent 2

node 2parent 2

node 3parent 3

Statusunion

Edge [1, 2]: different roots, so union them — node 1 now points at node 2.

What happens in this step

edge [1, 2]
find(1) → 1   find(2) → 2
roots differ → union: parent[1] = 2
parent array (index 1..3): [1, 2, 3] → [2, 2, 3]

Nodes 1 and 2 merge, with root 2 now representing both.

Step 1 of 3

Steps to visualize

The row has one cell per node (nodes are labelled 1, 2, 3). Each cell shows that node's current parent; a node pointing at itself is a root.
Give every node its own group, so each node starts as its own parent.
For each edge [a, b] in order, compare find(a) and find(b); the frame covers the two nodes of that edge.
If they already match, this edge is redundant — return it immediately.
Otherwise union a and b and continue to the next edge.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union edges in order, stop at the first repeat root

node 1parent 2

node 2parent 2

node 3parent 3

Statusunion

Edge [1, 2]: different roots, so union them — node 1 now points at node 2.

What happens in this step

edge [1, 2]
find(1) → 1   find(2) → 2
roots differ → union: parent[1] = 2
parent array (index 1..3): [1, 2, 3] → [2, 2, 3]

Nodes 1 and 2 merge, with root 2 now representing both.

Step 1 of 3

4. Solution

Solution

solution.tsTypeScript

function findRedundantConnection(edges) {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);

  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  for (const [a, b] of edges) {
    const rootA = find(a);
    const rootB = find(b);

    if (rootA === rootB) {
      return [a, b];
    }

    parent[rootA] = rootB;
  }

  return [];
}

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

5. Test cases

Test cases

Input	Expected	Covers
`edges = [[1,2],[1,3],[2,3]]`	`[2,3]`	example from the docstring
`edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]`	`[1,4]`	the redundant edge appears in the middle of the list
`edges = [[1,2],[2,3],[3,1]]`	`[3,1]`	smallest possible cycle, three nodes
`edges = [[1,4],[3,4],[1,3],[1,2]]`	`[1,3]`	the redundant edge is found before the last edge in the list is even reached
`edges = [[1,2],[1,3],[1,4],[3,4]]`	`[3,4]`	every earlier node attaches directly to node 1 before the cycle closes
`edges = [[1,2],[2,3],[3,4],[4,1]]`	`[4,1]`	a longer cycle spanning all four nodes

Redundant Connection