Redundant Connection

Medium

The edge that closes a cycle

Problem

In a tree with one extra edge added, return the edge that can be removed to make it a tree again.

In simple words

Union-find each edge; the first edge joining two already-connected nodes is the extra one.

The idea

Process the edges in order with union-find; the first edge whose endpoints already share a root is the one completing a cycle. Because the input is a tree plus one edge, that edge is the answer.

The trick

Return the last such edge if the problem asks for it explicitly.
Union-find makes the check O(α(n)) per edge.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: edges = [[1,2],[1,3],[2,3]]
Output:: [2, 3]
Explanation:: [2,3] closes a cycle → it's redundant.

Example 2

Input:: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output:: [1, 4]
Explanation:: [1,4] forms the loop.

Example 3

Input:: edges = [[1,2],[2,3]]
Output:: []
Explanation:: A tree has no redundant edge.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.