DSA Tracker

Visualize

Redundant Connection

Union-Find: the edge whose endpoints already share a root

time O(n α(n))space O(n)

A tree on n nodes has exactly n - 1 edges and no cycles, so one extra edge in the stream must be the one that closes a loop somewhere. You don't need to see the whole shape to find it: track, for every node, which connected group it belongs to (its DSU root), and merge two groups every time an edge joins them. The one edge whose two ends are ALREADY in the same group is the answer — nothing before it could have connected them any other way, so it is provably the newest cycle-closer. The badge on each node below is its current root.

Details

Animated on: 7 nodes, edges [1,2] [3,4] [1,3] [5,6] [1,5] [6,7] [4,7] in that order (an undirected tree plus one extra edge) — which edge can be removed to leave a valid tree?

Problem:Redundant ConnectionMedium

Pattern:Union Find

Union-Find: the edge whose endpoints already share a root

step 1 / 8

Stream of edges — one too many for a tree

7 nodes and 7 edges. A tree over 7 nodes needs exactly 6 edges, so this stream has one extra — process them left to right and the extra one reveals itself the instant its two ends already share a root.

Pseudocode
1FUNCTION findRedundant(n, edges):
2  FOR i FROM 1 TO n
3    parent[i] <- i
4  FOR EACH (u, v) IN edges
5    ru <- FIND(parent, u)
6    rv <- FIND(parent, v)
7    IF ru = rv
8      RETURN [u, v]
9    UNION(parent, ru, rv)
10  RETURN []

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. 7 nodes and 7 edges. A tree over 7 nodes needs exactly 6 edges, so this stream has one extra — process them left to right and the extra one reveals itself the instant its two ends already share a root.
  2. Edge [1, 2]: root(1) = 1, root(2) = 2 — different trees, so union them under 1. The tree now has 1 edge.
  3. Edge [3, 4]: root(3) = 3, root(4) = 4 — different trees, so union them under 3. The tree now has 2 edges.
  4. Edge [1, 3]: root(1) = 1, root(3) = 3 — different trees, so union them under 1. The tree now has 3 edges.
  5. Edge [5, 6]: root(5) = 5, root(6) = 6 — different trees, so union them under 5. The tree now has 4 edges.
  6. Edge [1, 5]: root(1) = 1, root(5) = 5 — different trees, so union them under 1. The tree now has 5 edges.
  7. Edge [6, 7]: root(6) = 1, root(7) = 7 (flattening 6→1 along the way) — different trees, so union them under 1. The tree now has 6 edges.
  8. Edge [4, 7]: root(4) = 1 and root(7) = 1 (flattening 4→1 along the way) — the tree above already connects them, so this edge would close a cycle. RETURN [4, 7].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Redundant Connection in the editorAll Graph problemsBack to roadmap