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.
This approach leverages Tarjan's Algorithm to find bridges in an undirected graph. A bridge, also known as a critical connection, is an edge which, when removed, increases the number of connected components in a graph.
The main idea is to use a DFS traversal while keeping track of two things for each node:
During the DFS traversal, if a node discovers a node that was discovered earlier, we update the current node's lowest point based on the discovered node unless it is a direct parent of the current node which means it's a backtracking edge. If the lowest point of the descendant is greater than the discovery time of the current node, then the connection between them is a critical connection.
The code defines a function criticalConnections which constructs a graph from the given connections. It uses DFS traversal to calculate the disc and low values. The critical connections are collected in critical_edges list.
Python
C++
Java
JavaScript
C#
The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is also O(V + E) due to the graph representation and recursion stack.
The Union-Find approach is less direct for this problem as it better suits static connectivity queries, but it can verify the disconnection effect of removing an edge by checking connectivity before and after its removal.
Here, a variation of Kruskal's algorithm can be employed with additional tracking to retry connections and verify their critical status. However, this requires additional complexity and is not the standard usage for critical connections.
So, while possible, using Union-Find isn't recommended due to its inefficiency in recomputing components with high time complexity.
The code implements a brute-force check of each edge's removal effect by rebuilding a Union-Find structure for each remaining connection set. It provides an intuitive understanding though not efficient for large inputs.
The time complexity on worst-case is O(E^2) due to the need for reconstructing the Union-Find structure. The space complexity is O(V) for the Union-Find structure.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) and Tarjan's Algorithm | The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is also O(V + E) due to the graph representation and recursion stack. |
| Union-Find with Path Compression | The time complexity on worst-case is O(E^2) due to the need for reconstructing the Union-Find structure. The space complexity is O(V) for the Union-Find structure. |
| 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 |
Critical Connections In a Network | Tarjans Algorithm for Bridge Detection | Leetcode 1192 • Tech Revisions • 42,365 views views
Watch 9 more video solutions →Practice Critical Connections in a Network with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor