Critical Connections in a Network
HardPrompt
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 != bi- There are no repeated connections.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through every connection in the network. For each connection, it is temporarily removed, and then the algorithm checks if the network remains connected. If the network becomes disconnected, the removed connection is identified as a critical connection.
Algorithm
- Initialize an empty list
critical_connectionsto store the results. - For each connection
(u, v)in the input listconnections:- Create a new graph by building an adjacency list from all connections except
(u, v). - Perform a graph traversal (e.g., DFS) starting from node 0 to count the number of reachable nodes.
- If the number of reachable nodes is less than
n, the graph is disconnected. Add the connection(u, v)tocritical_connections.
- Create a new graph by building an adjacency list from all connections except
- Return
critical_connections.
Walkthrough
The core idea is to simulate the removal of each edge one by one and test for graph connectivity.
First, we build an adjacency list representation of the graph from the input connections. We then loop through each edge (u, v) from the original connections list. Inside the loop, we create a temporary graph that excludes the current edge (u, v). We then perform a graph traversal, such as Depth-First Search (DFS) or Breadth-First Search (BFS), starting from an arbitrary node (e.g., node 0). We keep a count of the nodes visited during the traversal. After the traversal is complete, if the count of visited nodes is less than the total number of nodes n, it implies that the graph is disconnected. In this case, the edge (u, v) is a critical connection, and we add it to our result list. This process is repeated for all edges.
class Solution { public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) { List<List<Integer>> critical = new ArrayList<>(); for (int i = 0; i < connections.size(); i++) { // Build adjacency list for the graph without the i-th connection List<List<Integer>> adj = new ArrayList<>(); for (int j = 0; j < n; j++) { adj.add(new ArrayList<>()); } for (int j = 0; j < connections.size(); j++) { if (i == j) continue; List<Integer> edge = connections.get(j); adj.get(edge.get(0)).add(edge.get(1)); adj.get(edge.get(1)).add(edge.get(0)); } // Check for connectivity if (!isConnected(n, adj)) { critical.add(connections.get(i)); } } return critical; } private boolean isConnected(int n, List<List<Integer>> adj) { boolean[] visited = new boolean[n]; int[] count = {0}; // Start DFS from an arbitrary node (e.g., 0) dfs(0, adj, visited, count); return count[0] == n; } private void dfs(int u, List<List<Integer>> adj, boolean[] visited, int[] count) { visited[u] = true; count[0]++; for (int v : adj.get(u)) { if (!visited[v]) { dfs(v, adj, visited, count); } } }}Complexity
Time
O(E * (V + E)), where V is the number of servers (`n`) and E is the number of connections. For each of the E edges, we build a new adjacency list (which takes O(V+E)) and then perform a DFS/BFS (which also takes O(V+E)).
Space
O(V + E). In each iteration of the main loop, we build an adjacency list which requires O(V+E) space. The recursion stack for DFS can also go up to O(V).
Trade-offs
Pros
Simple to understand and implement.
Directly follows the definition of a critical connection, making the logic straightforward.
Cons
Highly inefficient due to its O(E * (V+E)) time complexity.
Rebuilds the graph and performs a full traversal for each edge, leading to a lot of redundant computation.
Will result in a "Time Limit Exceeded" error on large inputs as specified in the problem constraints.
Solutions
Solution
class Solution {private int now;private List<Integer>[] g;private List<List<Integer>> ans = new ArrayList<>();private int[] dfn;private int[] low;public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) { g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); dfn = new int[n]; low = new int[n]; for (var e : connections) { int a = e.get(0), b = e.get(1); g[a].add(b); g[b].add(a); } tarjan(0, -1); return ans; }private void tarjan(int a, int fa) { dfn[a] = low[a] = ++now; for (int b : g[a]) { if (b == fa) { continue; } if (dfn[b] == 0) { tarjan(b, a); low[a] = Math.min(low[a], low[b]); if (low[b] > dfn[a]) { ans.add(List.of(a, b)); } } else { low[a] = Math.min(low[a], dfn[b]); } } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.