Redundant Connection

Medium#684

A tree on vertices 1 to n got one extra edge, so the graph now has exactly one cycle. You get its n edges. Return an edge that can be removed so that a tree is left; if several fit, the one that comes last in the list. Our example: [1, 2], [3, 4], [2, 4], [3, 1], [4, 5] → [3, 1].

684 Redundant ConnectionWalkthrough · 1×

Example: [1, 2], [3, 4], [2, 4], [3, 1], [4, 5]. The cycle is 1–2–4–3–1, and its last edge in the list, 3–1, joins two vertices that are connected already. 4–5 comes after it, but is not on the cycle.

123451122334455parentedges1–23–42–43–14–5
looking at nowroot of a groupedge already addedthe edge that closes the cyclenever looked at

Each of the 5 vertices is its own root. Slot 0 is unused: vertices are numbered from 1

01/51
restart · back · play · step
Speed
1function findRedundantConnection(edges):
2 parent = [0, 1, ..., n] // n edges, vertices 1..n
3 for (a, b) in edges:
4 rootA = find(a)
5 rootB = find(b)
6 if rootA == rootB:
7 return [a, b]
8 parent[rootB] = rootA
9
10function find(x):
11 while parent[x] is not x:
12 x = parent[x]
13 return x
state
parent
[0, 1, 2, 3, 4, 5]
a
–
b
–
rootA
–
rootB
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. While the ends of an edge have different roots, the edge only joins two groups and adds no cycle. An edge whose ends already share a root has a path beside it, so together they make a cycle.
  2. A cycle is complete only when the last of its edges in the list arrives, so the first edge found this way is the cycle edge that comes last: the very one to return.
  3. Edges after it are not on the cycle, since the graph has only one, so the run stops there.

Complexity

Time O(n · h): two finds per edge, as deep as the trees, which is up to n here and almost a constant with re-hanging on the root and the smaller tree under the bigger. Memory O(n) for parent.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.