606. Critical Connections in a Network
A data center has n servers, numbered 0 to n - 1, wired together by undirected cables: connections[i] = [a, b] means servers a and b are directly linked. The network is connected — today, every server can reach every other, possibly through intermediaries.
A connection is critical if cutting that one cable would split the network, leaving some pair of servers unable to communicate. (Graph theory calls these edges bridges.)
Your function receives n and the list connections, and must return all critical connections, as a list of [a, b] pairs. Return them in any order, with each pair's endpoints in any order — the output is normalized before checking. A network can also have no critical connections at all (every cable sits on a cycle), in which case return an empty list.
Example 1:
Input: n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
Output: [[1, 3]]
Explanation: Servers 0, 1, 2 form a triangle, so cutting any one of those three cables still leaves a detour. The cable 1–3 is the only path to server 3 — cut it and 3 is stranded, so [1, 3] is critical.
Example 2:
Input: n = 5, connections = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]
Output: []
Explanation: The five servers form a single ring. Every cable has the rest of the ring as a backup path, so no connection is critical and the answer is the empty list.
Constraints:
- 2 ≤ n ≤ 2000
- 1 ≤ connections.length ≤ 5000
- connections[i] = [a, b] with 0 ≤ a, b < n and a ≠ b
- No cable appears twice, and the network is connected
Hints:
Brute force is legitimate here: remove one edge, run a BFS/DFS, and see whether the two endpoints can still reach each other. That is O(E · (V + E)) — fine for small graphs, and a great oracle to test a faster solution against.
An edge is NOT a bridge exactly when it lies on some cycle. So the real question is: during one DFS, which tree edges have no back edge 'jumping over' them?
Tarjan's bridge algorithm: give every node a discovery time disc[v], and compute low[v] = the smallest discovery time reachable from v's subtree using tree edges plus at most one back edge. A tree edge parent→child is a bridge iff low[child] > disc[parent]. Skip only the edge you arrived by (compare edge ids, not parent nodes).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
Expected output: [[1, 3]]