Critical Connections in a Network
Hard · Graphs · Depth-First Search · Graph · Biconnected Component
Problem
There are n servers numbered 0 to n - 1, linked by undirected connections, where connections[i] = [a, b] links servers a and b. Every server can reach every other server through the network.
A critical connection is a link whose removal would leave some server unable to reach some other server.
Return all critical connections, in any order. Each may be written as [a, b] or [b, a].
Examples
Input: n = 5, connections = [[0,1],[1,2],[2,0],[1,3],[3,4]] Output: [[3,4],[1,3]]
The ring 0-1-2 survives any single cut, but 1-3 and 3-4 are the only links to servers 3 and 4.
Input: n = 2, connections = [[0,1]] Output: [[0,1]]
The only link is critical.
Input: n = 4, connections = [[0,1],[1,2],[2,3],[3,0]] Output: []
Every link is on the ring, so none is critical.
Constraints
- 2 <= n <= 10^5
- n - 1 <= len(connections) <= 10^5
- 0 <= a, b < n and a != b
- No link is repeated
Approaches
- Remove each link and test connectivity — time O(m · (n + m)), space O(n + m)
Follow-up
What about critical servers (cut points)? The same disc and low values decide it: a non-root server u is critical when some child has low[child] >= disc[u], and the root when it has two or more DFS children. And if the network changed link by link, you would need a dynamic connectivity structure rather than one DFS.
Related problems
Start free on Cariara · Coding problems · System design studio
