The Extra Cable
MediumGraphs
Problem
A network of routers numbered 0 to n - 1 was wired as a tree: every router reachable, no loops. Then one extra cable was added between two different routers. The resulting n cables are listed in cables, so n = cables.length.
Return the cable that can be removed so that the network is a tree again. If several cables qualify, return the one that appears last in cables. Return it exactly as it is written in the input.
Example 1
- Input:
- cables = [[0, 1], [0, 2], [1, 2]]
- Output:
- [1, 2]
Any of the three cables could go; [1, 2] is the last.
Example 2
- Input:
- cables = [[0, 1], [1, 2], [2, 3], [1, 3], [0, 4]]
- Output:
- [1, 3]
The loop is 1–2–3–1; of its cables, [1, 3] appears last.
Constraints
- 3 ≤ n = cables.length ≤ 10^4
- 0 ≤ a, b < n, a ≠ b
- No cable is listed twice.
- The input is a tree plus exactly one extra cable.
Hint
Show the first hint
The extra cable created exactly one loop. Which cables are candidates for removal?
Walkthrough
How to approach it
01Clarify before coding
- Is there exactly one extra cable? Yes, so there is exactly one loop.
- Which answer if several work? The latest one in the list.
- Should the answer be normalised, e.g. smaller end first? No, return it exactly as listed.
02Brute force
For each cable from last to first, remove it and check with BFS whether the rest is connected and acyclic.
Cost: O(n) removals × O(n) per check = O(n²): 10^8 steps at n = 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.