Description
Find all critical connections (bridges) in a network. A connection is critical if removing it disconnects the network. Use Tarjan's algorithm.
Examples
Input:
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]Output:
[[1,3]]Explanation:
Removing [1,3] disconnects node 3 from the network.
Input:
n = 4, connections = [[1]]Output:
[1]Explanation:
Minimal case with a single-element matrix.
Input:
n = 6, connections = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,3]]Output:
[[0,1],[1,2],[2,3]]Explanation:
The network has a cycle between nodes 3,4,5. Removing any edge in this cycle (like [3,4], [4,5], or [5,3]) won't disconnect the network since there's an alternate path. However, edges [0,1], [1,2], and [2,3] are bridges because removing any of them would isolate parts of the network from the rest.
Constraints
- •
2 ≤ n ≤ 10⁵ - •
n - 1 ≤ connections.length ≤ 10⁵