DSA problem
Critical Connections in a Network
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network. A CRITICAL CONNECTION is a connection that, if removed, will make some servers unable to reach some other servers. Return all critical connections in the network in any order.
A critical connection is exactly a BRIDGE in graph theory: an edge whose removal disconnects the graph. The classical algorithm for finding all bridges is Tarjan's linear-time DFS, which runs in O(V + E).
Tarjan's bridge algorithm maintains two integer arrays per node: disc[u] (the DFS discovery timestamp of u) and low[u] (the smallest discovery time reachable from u by descending the DFS tree and then taking AT MOST ONE back edge). During DFS at u, for each neighbor v: if v is unvisited, recurse and then update low[u] = min(low[u], low[v]); after that, if low[v] > disc[u], then the edge (u, v) is a bridge — there is no alternative path from v back to u or higher. If v is already visited AND is not the parent of u, it is a back edge: low[u] = min(low[u], disc[v]).
Care must be taken with the parent check in undirected graphs: when recursing from u to v, the immediate return edge v -> u is not a back edge. The algorithm visits each vertex and each edge once, so total time and space are O(V + E).
Examples
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]][[1,3]]n = 2, connections = [[0,1]][[0,1]]n = 5, connections = [[0,1],[1,2],[2,3],[3,4],[4,2]][[0,1],[1,2]]Constraints
- 2 <= n <= 10^5
- n - 1 <= connections.length <= 10^5
- 0 <= a, b <= n - 1
- a != b
- There are no repeated connections.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.