Ctrl K

Fragile Network Cables

Hard
A data centre has count servers numbered 0 to count - 1. The cable cables[i] = [a, b] directly links servers a and b, and data flows through it both ways. Right now every server can reach every other one, directly or through a chain of servers. A cable is fragile if, once it breaks, there are two servers that can no longer reach each other. Return all fragile cables as pairs [a, b]. Neither the order of the pairs nor the order of servers inside a pair matters.
Example 1
count=5, cables=[[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]] → [[3, 4], [2, 3]]

Servers 0, 1, 2 form a ring, so any ring cable can be lost. Without [2, 3] or [3, 4], however, servers 3 and 4 are cut off. The pairs may be returned in any order, e.g. [[3, 4], [2, 3]].

Example 2
count=4, cables=[[0, 1], [1, 2], [2, 3], [3, 0]] → []

All four servers sit on a ring: whichever cable breaks, the network stays connected.

Example 3
count=3, cables=[[1, 0], [1, 2]] → [[1, 2], [0, 1]]
Constraints
  • 2 ≤ count ≤ 10⁵
  • count − 1 ≤ len(cables) ≤ 10⁵
  • 0 ≤ a, b < count, a ≠ b
  • Any two servers are linked by at most one cable
  • The network is connected
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsLetter Order From a Dictionary HardLongest Uphill Walk HardRoute Through Every Boarding Pass HardBall Into the Hole HardThe Extra Link in a Rooted Tree Hard
loading Python…
Input
count=5, cables=[[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]]
Expected
[[3, 4], [2, 3]]

Run checks the first 3 tests in your browser. Submit checks all 62 tests on the server, hidden ones included.