LeetCode 684 · Union–Find · Cycle

Redundant Connection

MediumFind the edge that closes a cycle in a tree-plus-one-edge graph.
You are given a graph that started as a tree with n nodes (labelled 1..n) and had exactly one extra edge added. The result has one cycle. Return the edge that can be removed so the graph is a tree again. If there are several answers, return the one that appears last in the input.

Walkthrough

edges:
[1,2]
[1,3]
[3,4]
[2,4]
1
def find(x):
2
    while parent[x] != x:
3
        x = parent[x]
4
    return x
5
6
for u, v in edges:
◄
7
    ru, rv = find(u), find(v)
8
    if ru == rv:
9
        return [u, v]   # redundant
10
    parent[ru] = rv      # union
no locals yet
1234
parent
1
1
2
2
3
3
4
4
STEP 0 / 46 · line 6
Start
parent[x] = x for all nodes. Loop over edges left to right.

Intuition

A tree with n nodes has exactly n−1 edges and no cycles. Adding one more edge creates exactly one cycle.

Process edges in order and keep a Union–Find (disjoint-set) of which nodes are already connected.

For each edge (u, v): if u and v already share a root, this edge connects two nodes that were reachable from one another — it closes the cycle and is the redundant one.

Otherwise the edge joins two separate components, so union them and keep going.

The algorithm

  1. 01Initialise parent[x] = x for every node (each node is its own root).
  2. 02find(x): follow parent pointers up until you reach a root (parent[x] == x).
  3. 03For each edge (u, v) compute ru = find(u) and rv = find(v).
  4. 04If ru == rv the two ends are already connected → return [u, v].
  5. 05Else set parent[ru] = rv to merge the two trees and continue.

Reference implementation

1
function findRedundantConnection(edges) {
2
  const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);
3
4
  const find = (x) => {
5
    while (parent[x] !== x) x = parent[x];
6
    return x;
7
  };
8
9
  for (const [u, v] of edges) {
10
    const ru = find(u), rv = find(v);
11
    if (ru === rv) return [u, v]; // redundant
12
    parent[ru] = rv;              // union
13
  }
14
  return [];
15
}

Complexity

Time
O(n · α(n)) — near-linear; α is the inverse Ackermann function.
Space
O(n) for the parent array.