Critical Connections in a Network

Hard

#1117Time: 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).1 company

Algorithms

Depth-First Search

Data structures

Graph

Companies

Akuna Capital

Prompt

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i. 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 <= 10⁵
n - 1 <= connections.length <= 10⁵
0 <= a_i, b_i <= n - 1
a_i != b_i
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_connections to store the results.
For each connection (u, v) in the input list connections:
- 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) to critical_connections.
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.

1class Solution {2    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {3        List<List<Integer>> critical = new ArrayList<>();4        5        for (int i = 0; i < connections.size(); i++) {6            // Build adjacency list for the graph without the i-th connection7            List<List<Integer>> adj = new ArrayList<>();8            for (int j = 0; j < n; j++) {9                adj.add(new ArrayList<>());10            }11            12            for (int j = 0; j < connections.size(); j++) {13                if (i == j) continue;14                List<Integer> edge = connections.get(j);15                adj.get(edge.get(0)).add(edge.get(1));16                adj.get(edge.get(1)).add(edge.get(0));17            }18            19            // Check for connectivity20            if (!isConnected(n, adj)) {21                critical.add(connections.get(i));22            }23        }24        return critical;25    }26    27    private boolean isConnected(int n, List<List<Integer>> adj) {28        boolean[] visited = new boolean[n];29        int[] count = {0};30        // Start DFS from an arbitrary node (e.g., 0)31        dfs(0, adj, visited, count);32        return count[0] == n;33    }34    35    private void dfs(int u, List<List<Integer>> adj, boolean[] visited, int[] count) {36        visited[u] = true;37        count[0]++;38        for (int v : adj.get(u)) {39            if (!visited[v]) {40                dfs(v, adj, visited, count);41            }42        }43    }44}

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.

This is an efficient, single-pass algorithm that uses Depth-First Search (DFS) to find all bridges (critical connections) in a graph. It works by keeping track of the discovery time of each node and the lowest discovery time reachable from it, allowing it to identify bridges in linear time.

Algorithm

Build an adjacency list representation of the graph.
Initialize disc and low arrays of size n with a sentinel value (e.g., -1).
Initialize a global time counter to 0.
Initialize an empty list bridges to store the results.
Define a DFS function dfs(u, parent).
Inside dfs(u, parent):
- Set disc[u] = low[u] = time++.
- For each neighbor v of u:
  - If v is parent, continue.
  - If v is visited (disc[v] != -1), update low[u] = min(low[u], disc[v]).
  - If v is not visited, recursively call dfs(v, u). After the call returns, update low[u] = min(low[u], low[v]).
  - Check if low[v] > disc[u]. If true, the edge (u, v) is a bridge. Add it to the bridges list.
Start the traversal by calling dfs(0, -1) (since the graph is connected).
Return the bridges list.

Walkthrough

The algorithm is based on a single DFS traversal of the graph. During the traversal, we maintain two key pieces of information for each node u:

disc[u]: The discovery time, which is the step/time when u is first visited.
low[u]: The "low-link" value, which is the lowest discovery time reachable from u (including itself) by traversing zero or more tree edges in the DFS tree and at most one back-edge.

We initialize disc and low arrays with a sentinel value (like -1). We also need an adjacency list for the graph and a global timer. We start the DFS from an arbitrary node. Let's say our DFS function is dfs(u, parent).

When we visit a node u:

We set disc[u] and low[u] to the current time, and then increment time.
We iterate through u's neighbors v.
If v is the parent that we came from, we skip it.
If v has been visited (i.e., disc[v] is not -1), it means we've found a back-edge. A back-edge from u to an ancestor v provides an alternative path. We update low[u] = min(low[u], disc[v]).
If v has not been visited, it's a new node in our DFS tree. We make a recursive call dfs(v, u).
After the recursive call for v returns, the low[v] value has been fully computed for the subtree rooted at v. We can use this to update u's low-link value: low[u] = min(low[u], low[v]).
Now, we check the bridge condition. The edge (u, v) is a bridge if the subtree rooted at v has no back-edge connection to u or any of its ancestors. This is true if low[v] > disc[u]. If this condition holds, we've found a critical connection and add (u, v) to our result list.

1import java.util.*;2 3class Solution {4    private int time = 0;5    private List<List<Integer>> adj;6    private int[] low;7    private int[] disc;8    private List<List<Integer>> bridges;9 10    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {11        // Build adjacency list12        adj = new ArrayList<>();13        for (int i = 0; i < n; i++) {14            adj.add(new ArrayList<>());15        }16        for (List<Integer> conn : connections) {17            int u = conn.get(0);18            int v = conn.get(1);19            adj.get(u).add(v);20            adj.get(v).add(u);21        }22 23        // Initialize arrays24        low = new int[n];25        disc = new int[n];26        Arrays.fill(disc, -1); // -1 indicates unvisited27        bridges = new ArrayList<>();28 29        // Start DFS from node 0 (since the graph is connected)30        // The parent of the starting node can be a sentinel value like -131        dfs(0, -1);32 33        return bridges;34    }35 36    private void dfs(int u, int parent) {37        disc[u] = low[u] = time++;38        39        for (int v : adj.get(u)) {40            if (v == parent) {41                continue; // Skip the edge back to the parent42            }43            44            if (disc[v] != -1) { // v is a visited node (a back-edge)45                low[u] = Math.min(low[u], disc[v]);46            } else { // v is an unvisited node (a tree-edge)47                dfs(v, u);48                // After visiting v's subtree, update low[u]49                low[u] = Math.min(low[u], low[v]);50                51                // Check for bridge condition52                if (low[v] > disc[u]) {53                    bridges.add(Arrays.asList(u, v));54                }55            }56        }57    }58}

Complexity

Time

O(V + E). The algorithm is based on a single DFS traversal. Every vertex and every edge is visited exactly once.

Space

O(V + E). This is for storing the adjacency list (O(V+E)), the `disc` and `low` arrays (O(V)), and the recursion stack for DFS (O(V) in the worst case).

Trade-offs

Pros

Highly efficient, with linear time complexity.
Solves the problem in a single pass over the graph.
It's the standard and optimal algorithm for finding bridges in a graph.

Cons

More complex to understand and implement compared to the brute-force approach.
Requires a good understanding of Depth-First Search and its properties, specifically back-edges and DFS trees.

Solutions

Solution

1class Solution {2private3  int now;4private5  List<Integer>[] g;6private7  List<List<Integer>> ans = new ArrayList<>();8private9  int[] dfn;10private11  int[] low;12public13  List<List<Integer>> criticalConnections(int n,14                                          List<List<Integer>> connections) {15    g = new List[n];16    Arrays.setAll(g, k->new ArrayList<>());17    dfn = new int[n];18    low = new int[n];19    for (var e : connections) {20      int a = e.get(0), b = e.get(1);21      g[a].add(b);22      g[b].add(a);23    }24    tarjan(0, -1);25    return ans;26  }27private28  void tarjan(int a, int fa) {29    dfn[a] = low[a] = ++now;30    for (int b : g[a]) {31      if (b == fa) {32        continue;33      }34      if (dfn[b] == 0) {35        tarjan(b, a);36        low[a] = Math.min(low[a], low[b]);37        if (low[b] > dfn[a]) {38          ans.add(List.of(a, b));39        }40      } else {41        low[a] = Math.min(low[a], dfn[b]);42      }43    }44  }45}

1class Solution {2public:3  vector<vector<int>> criticalConnections(int n,4                                          vector<vector<int>> &connections) {5    int now = 0;6    vector<int> dfn(n);7    vector<int> low(n);8    vector<int> g[n];9    for (auto &e : connections) {10      int a = e[0], b = e[1];11      g[a].push_back(b);12      g[b].push_back(a);13    }14    vector<vector<int>> ans;15    function<void(int, int)> tarjan = [&](int a, int fa) -> void {16      dfn[a] = low[a] = ++now;17      for (int b : g[a]) {18        if (b == fa) {19          continue;20        }21        if (!dfn[b]) {22          tarjan(b, a);23          low[a] = min(low[a], low[b]);24          if (low[b] > dfn[a]) {25            ans.push_back({a, b});26          }27        } else {28          low[a] = min(low[a], dfn[b]);29        }30      }31    };32    tarjan(0, -1);33    return ans;34  }35};

1class Solution:2    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]: def tarjan(a: int, fa: int): nonlocal now now += 1 dfn[a] = low[a] = now for b in g[a]: if b == fa: continue if not dfn[b]: tarjan(b, a) low[a] = min(low[a], low[b]) if low[b] > dfn[a]: ans . append([a, b]) else: low[a] = min(low[a], dfn[b]) g = [[] for _ in range(n)] for a, b in connections: g[a]. append(b) g[b]. append(a) dfn = [0] * n low = [0] * n now = 0 ans = [] tarjan(0, - 1) return ans

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.

← Previous

Previous problem

Next problem