Watch 10 video solutions for Critical Connections in a Network, a hard level problem involving Depth-First Search, Graph, Biconnected Component. This walkthrough by Tech Revisions has 42,365 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some servers unable to reach some other server.
Return all critical connections in the network in any order.
Example 1:
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted.
Example 2:
Input: n = 2, connections = [[0,1]] Output: [[0,1]]
Constraints:
2 <= n <= 105n - 1 <= connections.length <= 1050 <= ai, bi <= n - 1ai != biProblem Overview: You are given n servers connected by bidirectional edges. A connection is critical if removing it disconnects part of the network. The task is to return all such edges, also known as bridges in graph theory.
Approach 1: Edge Removal + Connectivity Check (Brute Force) (Time: O(E * (V + E)), Space: O(V + E))
Remove each edge one at a time and run a DFS or BFS to check whether the graph is still fully connected. If the number of reachable nodes decreases, that edge is a critical connection. Implementation is straightforward: build the adjacency list, temporarily skip the tested edge, then run a traversal from any node. This approach works for small graphs but becomes expensive because you repeat a full traversal for every edge.
Approach 2: Union-Find Connectivity Testing (Time: O(E² α(V)), Space: O(V))
Another option rebuilds connectivity using a Union-Find structure for each edge exclusion. For every edge (u, v), rebuild the disjoint set using all other edges and check whether u and v remain connected. Path compression and union by rank make each union nearly constant time, but rebuilding the structure repeatedly still leads to quadratic behavior. This approach helps demonstrate connectivity reasoning but is rarely the optimal bridge detection method.
Approach 3: DFS with Tarjan's Algorithm (Optimal) (Time: O(V + E), Space: O(V))
The optimal solution uses a single Depth-First Search traversal combined with Tarjan's bridge-finding technique. Each node records two values: its discovery time and the lowest discovery time reachable through its subtree (low). While exploring neighbors, update the low-link values using back edges. If for an edge (u, v) the condition low[v] > disc[u] holds, there is no alternative path from v back to u or its ancestors, meaning the edge is a bridge. This method processes every vertex and edge exactly once, making it linear time. It is a standard technique in graph problems involving bridges and biconnected components.
Recommended for interviews: Interviewers expect the Tarjan DFS solution because it demonstrates strong graph fundamentals and understanding of bridge detection. Mentioning the brute force edge-removal idea first shows problem intuition, but implementing the linear-time Tarjan approach signals deeper algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Edge Removal + DFS/BFS | O(E * (V + E)) | O(V + E) | Conceptual brute force approach for understanding bridges |
| Union-Find Rebuild per Edge | O(E² α(V)) | O(V) | When experimenting with connectivity structures like disjoint sets |
| DFS with Tarjan's Algorithm | O(V + E) | O(V) | Optimal solution for detecting bridges in undirected graphs |