785. Bridges in the Network
A campus network has n switches numbered 0 to n - 1, joined by two-way cables listed in connections; each entry [a, b] is one cable between switches a and b. The same pair may be cabled more than once, and the network may be split into several separate parts.
A cable is fragile if unplugging just that cable leaves some pair of switches that could talk to each other before unable to do so afterwards. Return all fragile cables, each written as [x, y] with x < y. Sort the list in ascending order by x, then by y. If no cable is fragile, return an empty list.
Example 1
- Input:
- n = 6connections = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,3]]
- Output:
- [[2,3]]
- Explanation:
Cables 0-1, 1-2, 2-0 form a loop and 3-4, 4-5, 5-3 form another, so only the link 2-3 between the two loops is a bridge.
Example 2
- Input:
- n = 4, connections = [[0,1],[1,2],[2,3]]
- Output:
- [[0,1],[1,2],[2,3]]
- Explanation:
The network is a single line, so removing any of the three cables splits it; all three are bridges.
Example 3
- Input:
- n = 5, connections = [[0,1],[0,1],[1,2],[3,4]]
- Output:
- [[1,2],[3,4]]
- Explanation:
The cable 0-1 is doubled so it is not a bridge, while 1-2 and 3-4 are the only connections of their parts: [[1, 2], [3, 4]].
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ connections.length ≤ 2 * 105
- 0 ≤ a, b < n and a ≠ b
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n + m + b log b)
- Space
- O(n + m)