Which cable closes a loop?

Graphs Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
boss = list(range(5))

def find(x: int) -> int:
    while boss[x] != x:
        x = boss[x]
    return x

closing = None
for a, b in [(1, 2), (2, 3), (3, 4), (1, 4)]:
    ra, rb = find(a), find(b)
    if ra == rb:
        closing = (a, b)
    else:
        boss[ra] = rb
print(closing)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A (1, 4)

Right: 1 and 4 are already linked through 2 and 3.

Union-find answers 'already connected?' in near-constant time, so the closing cable shows up the moment it is laid.

Why not the others?
  • B (3, 4). When (3, 4) is laid, 4 is still on its own.
  • C None. The fourth cable joins two offices that are already connected.

30-second answer

Lay the cables in list order with union-find. The first cable whose two ends are already connected closes the loop. Every other cable on that loop came earlier in the list (they had to, to connect its ends), so this one is also the last loop cable in the list. O(n·α(n)) time and O(n) space.

Practise saying it · 45 s. No recording, just a timer

Explain how to find the cable that makes a loop.

Say your answer out loud, then check which of these points you covered:

  • Union-find in cable order
  • Already connected means loop
  • Near O(n)

Deep dive

Any cable on the loop can be removed to leave a tree; the 'last in the list' rule makes the answer unique.

DFS per cable to test connectivity is O(n²): fine as a first answer.

Union-find is the natural tool whenever edges arrive one by one.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def closing_cable(cables: list[list[int]]) -> list[int]:
    boss = list(range(len(cables) + 1))

    def find(x: int) -> int:
        while boss[x] != x:
            boss[x] = boss[boss[x]]
            x = boss[x]
        return x

    for a, b in cables:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]
        boss[ra] = rb
    return []

Common mistakes

  • Returning the first cable on the loop rather than the one that closed it.
  • Off-by-one with 1-based office numbers.

Senior take & follow-ups

Walk through a four-office example in the order cables are laid; it makes the 'last one' rule clear.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if cables are one-way?

    Show hint

    The directed version needs extra care for nodes with two parents.

  2. How would you find all cables on the loop?

    Show hint

    DFS from one end to the other in the tree without the extra cable.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.