Fragile Network Links
MediumAdvanced Graphs
Problem
An office network has n switches and a list of cables links[i] = [u, v] (undirected; two switches may be joined by more than one cable).
A cable is fragile if cutting it alone increases the number of disconnected groups of switches. Return every fragile cable as [min(u, v), max(u, v)], with the list sorted in ascending order (by first switch, then second).
Example 1
- Input:
- n = 5, links = [[0,1],[1,2],[2,0],[1,3],[3,4]]
- Output:
- [[1,3],[3,4]]
Cables inside the triangle 0-1-2 have a backup route; 1–3 and 3–4 do not.
Example 2
- Input:
- n = 3, links = [[0,1],[1,2],[2,0]]
- Output:
- []
Example 3
- Input:
- n = 2, links = [[0,1]]
- Output:
- [[0,1]]
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ links.length ≤ 2·10^4
- u ≠ v
- The network may already be disconnected.
Hint
Show the first hint
Removing each cable and re-checking connectivity works but costs O(E·(n + E)).
Walkthrough
How to approach it
01Clarify before coding
- Can there be parallel cables? Yes, and a doubled cable is never fragile.
- Is the network connected? Not necessarily; run DFS from every unvisited switch.
- Output format? Each pair as [smaller, larger], the list sorted.
02Brute force
For each cable, remove it, run BFS, and see whether its two ends are still connected.
Cost: O(E · (n + E)) ≈ 2·10^4 · 3·10^4 = 6·10^8 steps: too slow.
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.