Critical Connections in a Network
A network of n servers is connected by undirected links so that every server can reach every other. A link is critical if removing it disconnects some pair of servers. Return all critical links.
- 2 ≤ n ≤ 10^5
- n - 1 ≤ connections.length ≤ 10^5
- No repeated links
- Edges whose removal disconnects the graph = bridges
- An edge is a bridge if the subtree below it cannot reach an ancestor
- DFS discovery times and low-link values
DFS follows one branch to exhaustion before backtracking, which makes it the natural tool for "which cells/nodes belong together", for enumerating complete paths, and for cycle detection via the recursion stack (gray nodes). It needs only the graph plus a visited set and is easily written recursively.
Run a DFS assigning each node a discovery time disc[u] and a low[u] — the smallest discovery time reachable from u's subtree via at most one back edge. After exploring child v, set low[u] = min(low[u], low[v]); if low[v] > disc[u], no path from v's subtree returns above u, so edge (u, v) is a bridge. Back edges (excluding the edge to the parent) update low[u] with disc[v].
- Removing each edge and testing connectivity is O(E · (V + E)). An iterative DFS is needed in practice at 10^5 nodes to avoid recursion limits.