codejump
HardPro challengePythonJavaScriptTypeScript

Graph — Critical Connections (Bridges)

Data StructuresGraphsDFSTarjan

solve(n, connections) — n servers 0..n-1 connected by undirected
cables. A cable is critical (a *bridge*) if removing it disconnects some servers
that were previously connected. The network is connected and has no repeated cable.

Return every critical cable as [a, b] with a < b, sorted by a then b.

Use Tarjan's bridge-finding algorithm: one DFS that records, for each node, its
discovery time disc and the lowest discovery time reachable from its subtree
low. A tree edge u → v is a bridge exactly when low[v] > disc[u].

Examples

solve(4, [[0,1],[1,2],[2,0],[1,3]])   → [[1,3]]
solve(2, [[0,1]])                     → [[0,1]]
solve(3, [[0,1],[1,2],[2,0]])         → []      // a cycle: every cable has a backup

Sample tests

Test #1One bridge hanging off a cycle
Input: [4,[[0,1],[1,2],[2,0],[1,3]]]
Output: [[1,3]]
Test #2Single edge
Input: [2,[[0,1]]]
Output: [[0,1]]
Test #3A cycle has no bridge
Input: [3,[[0,1],[1,2],[2,0]]]
Output: []