Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Redundant Connection

LeetCode #684Medium
Union-Find · first cycle-closing edge

A tree of n nodes had one extra edge added, creating exactly one cycle. Given the edges in input order, return the edge that can be removed so the result is again a tree — the last edge (in input order) that closes a cycle.

Asked atAmazonGoogle
step 1 / 8
graph + disjoint sets
1
2
3
parent[]
123
123
Union-Find detects the cycle
▸
1parent[i] ← i                       // each node its own set
2find(x): while parent[x] != x: x = parent[x]; return x
3for (a, b) in edges:
4    if find(a) == find(b): return [a, b]   // same set → cycle
5    parent[find(b)] = find(a)              // union
6// first same-set edge is the redundant one
state
  • edges[[1,2],[1,3],[2,3]]
  • parent[1,2,3]
  • sets3

line 1Redundant Connection (LeetCode 684): a tree had ONE extra edge added, so the graph has exactly one cycle. A tree on n nodes has n−1 edges and is acyclic, so the extra edge must connect two nodes that are ALREADY connected — closing a loop. Union-Find finds it: start with every node in its own set (parent[i] = i).