Graphs crash course ↗ · 100

684. Redundant Connection

A tree on n nodes has exactly n-1 edges. Given n edges, one must be extra. Sweep the edges in order with Union-Find: the first edge whose two endpoints already share a root is the one that creates a cycle — that's your answer.

● MediumUnion-FindGraph Cycle DetectionTypeScript

PROBLEM What we're solving

You're given an undirected graph that started as a tree and had one extra edge added to it. The input is a list of n edges forming a graph with n nodes (labeled 1 to n). Return the extra edge. If multiple edges could be removed to restore the tree, return the one that appears last in the input.

Concrete example: edges = [[1,2],[1,3],[2,3]] — the three edges connect three nodes, but a tree on 3 nodes only needs 2 edges. Edge [2,3] forms a triangle with the first two, so the answer is [2,3].

KEY IDEA The first edge that joins two already-connected nodes is the cycle-closer

Insight → maintain a Union-Find (disjoint-set) structure over the nodes. Process edges one by one. Before adding an edge [u, v], check whether u and v are already in the same component(same root). If they are, this edge would create a cycle — it's the answer. If not, union the two components and continue.

RECIPE Sweep edges, union components, return the first cycle-closer

  • 0 · Initialize. Allocate a parent array of size n + 1 where parent[i] = i — each node is its own root. (Size n + 1 so 1-indexed nodes work without offset arithmetic.)
  • 1 · For each edge [u, v]. Call find(u) and find(v) to locate their roots. find walks up the parent chain; use path-halving (parent[x] = parent[parent[x]]) so future finds are faster.
  • 2 · Cycle check. If find(u) === find(v), both nodes already belong to the same tree — adding this edge would close a cycle. Return [u, v] immediately.
  • 3 · Union. Otherwise, merge the two trees: parent[root(u)] = root(v). Continue to the next edge.
Classic confusion →beginners sometimes check for a cycle with DFS on the whole graph after building it. That works but re-runs in O(n) per query. With Union-Find each edge is processed once in near-constant time — there's no need to build an adjacency list at all. Another trap: forgetting that the problem asks for the lastsuch edge if there's ambiguity — but since a valid input has exactly one extra edge, the first cycle-closer is always the unique answer.

COST Complexity & alternatives

DFS / BFS cycle check
O(n²)
Re-traverse from scratch after each edge addition.
Union-Find (path compression)
O(n · α(n))
α is the inverse-Ackermann function — effectively O(n).

Space is O(n) for the parent array. Adding union-by-rank alongside path compression guarantees the inverse-Ackermann bound; path-halving alone is sufficient in practice.

Pattern transfer → the same Union-Find skeleton powers Number of Connected Components (684's sibling), Graph Valid Tree (check no cycle AND all nodes connected), Accounts Merge (union emails by account), and Redundant Connection II (directed graph variant, LeetCode 685).

RUN IT Union-Find: first edge that closes a cycle

step 0 / 7
STARTInitialize Union-Find: each of the 3 nodes is its own parent. We will process 3 edges one by one.
1▶function findRedundantConnection(edges: number[][]): number[] {
2▶  const parent: number[] = Array.from({ length: edges.length + 1 }, (_, i) => i);
3 
4  function find(x: number): number {
5    while (parent[x] !== x) {
6      parent[x] = parent[parent[x]]; // path-compression (halving)
7      x = parent[x];
8    }
9    return x;
10  }
11 
12  for (const [u, v] of edges) {
13    const ru = find(u);
14    const rv = find(v);
15    if (ru === rv) return [u, v];   // both already in same component → cycle
16    parent[ru] = rv;                // union: attach ru's tree under rv
17  }
18 
19  return []; // unreachable given valid input
20}
parent[]112233
edges: 1-21-32-3
State
[1,2,3]
parent
—
result
current edge / root being examinedunioned (merged) rootedge already processed (safe)redundant edge (cycle detected)
slowfast

TYPESCRIPT The solution, annotated

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

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path-compression (halving)
      x = parent[x];
    }
    return x;
  }

  for (const [u, v] of edges) {
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) return [u, v];   // both already in same component → cycle
    parent[ru] = rv;                // union: attach ru's tree under rv
  }

  return []; // unreachable given valid input
}

Reading it block by block

Line 2 — parent array. parent[i] = i initializes every node as its own root. We allocate edges.length + 1 slots because nodes are 1-indexed and the number of nodes equals the number of edges in this problem.
Lines 4–9 — find with path compression. Walking up the parent chain until parent[x] === x finds the root. The line parent[x] = parent[parent[x]] (path-halving) shortens the chain on every traversal, keeping future finds nearly O(1).
Lines 11–15 — main loop. For each edge, find both roots. If equal, the two nodes are already in the same component — this edge would close a cycle, so return it immediately. Otherwise, union by pointing ru's tree under rv.
Line 17 — unreachable return. The problem guarantees exactly one redundant edge, so the loop always returns early. The trailing return []satisfies TypeScript's control-flow checker.
Complexity → O(n · α(n)) time — the α (inverse-Ackermann) factor is at most 4 for any input that fits in the universe, so this is effectively O(n). O(n) space for the parent array. No adjacency list needed.

INTERVIEWFollow-ups they'll ask

  • "What if the graph is directed?" See LeetCode 685. A directed redundant edge must be the one that (a) has in-degree 2, or (b) closes a cycle — there are two distinct cases to handle.
  • "Can you add union-by-rank?" Track the size or rank of each component; always attach the smaller tree under the larger. Combined with path compression this proves the inverse-Ackermann bound rigorously.
  • "What if there are multiple redundant edges?"The problem guarantees exactly one, but if there were several you'd continue scanning and return the last one found (since the last one appears latest in the input).
  • "Could you solve this with DFS?"Yes — build an adjacency list, then for each edge check whether a path already exists via DFS before adding it. That's O(n²) overall versus Union-Find's near-linear.
  • "What does the parent array represent after the algorithm runs?"Each node's entry points (directly or indirectly) to the canonical root of its component. Calling find(x) resolves to that root, and all nodes with the same root are in the same connected component.

OPTIMAL Union-Find

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

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path-compression (halving)
      x = parent[x];
    }
    return x;
  }

  for (const [u, v] of edges) {
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) return [u, v];   // both already in same component → cycle
    parent[ru] = rv;                // union: attach ru's tree under rv
  }

  return []; // unreachable given valid input
}
Complexity → O(n · α(n)) time — the α (inverse-Ackermann) factor is at most 4 for any input that fits in the universe, so this is effectively O(n). O(n) space for the parent array. No adjacency list needed.

ALT 1 Brute force — DFS path check before adding each edge

O(n²) time · O(n) space

Build the graph incrementally. Before inserting edge [u, v], run a DFS to ask “is there already a path from u to v?” If so, this edge closes a cycle — it's the redundant one.

approach-2.ts
function findRedundantConnection(edges: number[][]): number[] {
  const adj = new Map<number, number[]>();

  function hasPath(u: number, v: number, seen: Set<number>): boolean {
    if (u === v) return true;
    seen.add(u);
    for (const next of adj.get(u) ?? []) {
      if (!seen.has(next) && hasPath(next, v, seen)) return true;
    }
    return false;
  }

  for (const [u, v] of edges) {
    // If u and v are already connected, this edge creates a cycle.
    if (adj.has(u) && adj.has(v) && hasPath(u, v, new Set<number>())) {
      return [u, v];
    }
    if (!adj.has(u)) adj.set(u, []);
    if (!adj.has(v)) adj.set(v, []);
    adj.get(u)!.push(v);
    adj.get(v)!.push(u);
  }

  return []; // unreachable given valid input
}
Note → Each of the n edges triggers a DFS that can visit up to nnodes, so the worst case is O(n²). Union-Find with path compression answers the same “already connected?” question in near-constant amortized time, dropping the total to O(n·α(n)).

MNEMONIC The one-liner

"Each node starts alone. The first edge that tries to marry two already-married nodes is the culprit."

TRIGGERS When you see ___ → reach for ___

"extra edge in a tree" / detect cycle in undirected graphUnion-Find over edges
merge connected components incrementallyparent[root(u)] = root(v)
"graph valid tree" or "connected components"same Union-Find skeleton
find(u) === find(v) before adding edgecycle-closing check → return edge

SKELETON The reusable shape

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

function find(x: number): number {
  while (parent[x] !== x) {
    parent[x] = parent[parent[x]]; // path-halving compression
    x = parent[x];
  }
  return x;
}

for (const [u, v] of edges) {
  const ru = find(u), rv = find(v);
  if (ru === rv) return [u, v];    // first cycle-closing edge
  parent[ru] = rv;                 // union
}

FLASHCARDS Tap to flip

What data structure powers the optimal solution?
Union-Find (Disjoint Set Union) — tracks which component each node belongs to.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
For edges = [[1,2],[1,3],[2,3]], what does the algorithm return?
QUESTION 02
What is the time complexity of the Union-Find approach with path compression?
QUESTION 03
Why do we allocate the parent array with size edges.length + 1 rather than edges.length?
QUESTION 04
What does the find() function return?
QUESTION 05
Path-halving sets parent[x] = parent[parent[x]]. What is the purpose?
QUESTION 06
You run the algorithm on [[1,2],[2,3],[3,4],[1,4],[1,5]]. Which edge is returned?
QUESTION 07
Which alternative correctly detects the redundant edge but with worse complexity?
QUESTION 08
#684 · Redundant ConnectionProcess edges in order with Union-Find: the first edge whose two endpoints already share a root forms the redundant cycle. O(n α(n)) overall.Which algorithmic approach does this primarily use?
QUESTION 09
#684 · Redundant ConnectionProcess edges in order with Union-Find: the first edge whose two endpoints already share a root forms the redundant cycle. O(n α(n)) overall.Which implementation correctly solves it?