Critical Connections in a Network
Description
You are given a network of n servers, numbered from 0 to n - 1, connected by undirected server-to-server connections. The connections are represented as a list where connections[i] = [a, b] means there is a direct link between server a and server b. Every server can communicate with every other server either directly or through a chain of intermediate servers.
A critical connection (also known as a bridge) is a connection that, if removed, would cause at least one pair of servers to lose their ability to communicate. In other words, removing a critical connection increases the number of disconnected groups in the network.
Your task is to identify and return all such critical connections in the network. The result can be returned in any order.
Examples
Example 1
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: Servers 0, 1, and 2 form a cycle (a triangle). Within this cycle, removing any single edge still leaves a path between those three servers. For instance, removing edge [0,1] still allows server 0 to reach server 1 via the path 0 → 2 → 1. However, server 3 is connected to the rest of the network only through edge [1,3]. If we remove [1,3], server 3 becomes completely isolated — there is no alternative route. Therefore, [1,3] is the only critical connection.
Example 2
Input: n = 2, connections = [[0,1]]
Output: [[0,1]]
Explanation: There are only two servers connected by a single edge. Removing this edge disconnects the entire network. Since it is the only path between server 0 and server 1, edge [0,1] is a critical connection.
Example 3
Input: n = 6, connections = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3]]
Output: [[1,3]]
Explanation: Servers 0, 1, 2 form a cycle and servers 3, 4, 5 form another cycle. These two cycles are joined only by edge [1,3]. Removing [1,3] splits the graph into two separate components: {0, 1, 2} and {3, 4, 5}. No other edge removal disconnects the graph, so [1,3] is the sole critical connection.
Constraints
- 2 ≤ n ≤ 10^5
- n - 1 ≤ connections.length ≤ 10^5
- 0 ≤ a_i, b_i ≤ n - 1
- a_i ≠ b_i
- There are no repeated connections.
Editorial
Brute Force
Intuition
The most straightforward way to find critical connections is to test each edge individually. For every edge in the graph, temporarily remove it and then check whether the graph is still fully connected. If removing an edge causes the graph to split into two or more disconnected parts, that edge is a critical connection (a bridge).
Think of it like testing each road on a map: block one road at a time, then try driving from every city to every other city. If any city becomes unreachable while a particular road is blocked, that road is critical infrastructure.
To check connectivity after removing an edge, we can run a BFS or DFS starting from any node and see if all nodes are still reachable.
Step-by-Step Explanation
Let's trace through with n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]:
Step 1: Build adjacency list. Node 0 connects to {1, 2}. Node 1 connects to {0, 2, 3}. Node 2 connects to {0, 1}. Node 3 connects to {1}.
Step 2: Remove edge [0,1]. Run DFS from node 0. We can reach: 0 → 2 → 1 → 3. All 4 nodes reachable. Edge [0,1] is NOT critical. Restore edge.
Step 3: Remove edge [1,2]. Run DFS from node 0. We can reach: 0 → 1 → 3, and 0 → 2 (via edge 0-2... wait, we also have 0-2 still). So 0 → 2, 0 → 1 → 3. All 4 nodes reachable. Edge [1,2] is NOT critical. Restore edge.
Step 4: Remove edge [2,0]. Run DFS from node 0. We can reach: 0 → 1 → 2, 0 → 1 → 3. All 4 nodes reachable. Edge [2,0] is NOT critical. Restore edge.
Step 5: Remove edge [1,3]. Run DFS from node 0. We can reach: 0 → 1 → 2, and that's it. Node 3 is NOT reachable! Only 3 of 4 nodes visited. Edge [1,3] IS a critical connection.
Step 6: Return result: [[1,3]].
Brute Force — Testing Each Edge for Bridge Property — Watch as we remove each edge one at a time and run DFS to check if the graph remains connected. When removing edge 1-3, node 3 becomes unreachable.
Algorithm
- Build an adjacency list from the connections.
- For each edge (u, v) in the connections:
a. Temporarily remove edge (u, v) from the adjacency list.
b. Run DFS or BFS from any node (e.g., node 0).
c. Count the number of nodes visited.
d. If visited count < n, the edge (u, v) is a critical connection — add it to the result.
e. Restore edge (u, v). - Return the list of critical connections.
Code
class Solution {
public:
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
// Build adjacency list
vector<set<int>> adj(n);
for (auto& conn : connections) {
adj[conn[0]].insert(conn[1]);
adj[conn[1]].insert(conn[0]);
}
vector<vector<int>> result;
for (auto& conn : connections) {
int u = conn[0], v = conn[1];
// Remove edge
adj[u].erase(v);
adj[v].erase(u);
// BFS/DFS to check connectivity
vector<bool> visited(n, false);
queue<int> q;
q.push(0);
visited[0] = true;
int count = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
count++;
q.push(neighbor);
}
}
}
if (count < n) {
result.push_back({u, v});
}
// Restore edge
adj[u].insert(v);
adj[v].insert(u);
}
return result;
}
};from collections import defaultdict, deque
class Solution:
def criticalConnections(self, n: int, connections: list[list[int]]) -> list[list[int]]:
# Build adjacency list using sets for easy removal
adj = defaultdict(set)
for u, v in connections:
adj[u].add(v)
adj[v].add(u)
result = []
for u, v in connections:
# Remove edge
adj[u].discard(v)
adj[v].discard(u)
# BFS to check connectivity
visited = set()
queue = deque([0])
visited.add(0)
while queue:
node = queue.popleft()
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
if len(visited) < n:
result.append([u, v])
# Restore edge
adj[u].add(v)
adj[v].add(u)
return resultclass Solution {
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
// Build adjacency list using sets
Set<Integer>[] adj = new HashSet[n];
for (int i = 0; i < n; i++) adj[i] = new HashSet<>();
for (List<Integer> conn : connections) {
adj[conn.get(0)].add(conn.get(1));
adj[conn.get(1)].add(conn.get(0));
}
List<List<Integer>> result = new ArrayList<>();
for (List<Integer> conn : connections) {
int u = conn.get(0), v = conn.get(1);
// Remove edge
adj[u].remove(v);
adj[v].remove(u);
// BFS to check connectivity
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
visited[0] = true;
int count = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
count++;
queue.offer(neighbor);
}
}
}
if (count < n) {
result.add(Arrays.asList(u, v));
}
// Restore edge
adj[u].add(v);
adj[v].add(u);
}
return result;
}
}Complexity Analysis
Time Complexity: O(E × (V + E))
For each of the E edges, we remove it and run a BFS/DFS that traverses all V vertices and E edges. This gives us E iterations, each costing O(V + E), for a total of O(E × (V + E)).
With E up to 10^5, this results in roughly 10^10 operations in the worst case — far too slow.
Space Complexity: O(V + E)
We store the adjacency list (O(V + E)) and the visited array (O(V)) for each BFS/DFS run.
Why This Approach Is Not Efficient
The brute force tests each edge independently by removing it and running a full graph traversal. With up to 10^5 edges and each traversal costing O(V + E), the total time is O(E × (V + E)) ≈ O(E² + VE). For the maximum constraints (V = 10^5, E = 10^5), this could mean up to 10^10 operations — well beyond the typical time limit.
The fundamental inefficiency is that we treat every edge removal as an independent problem, re-exploring the entire graph from scratch each time. We learn nothing from one test that could help with the next.
Key insight: Instead of testing edges independently, we can analyze the entire graph structure in a single DFS pass. If we track how "deeply" each node is embedded in the DFS tree and whether any descendant has a back-edge to an ancestor, we can determine which edges are bridges without ever removing them. This is the foundation of Tarjan's Bridge-Finding Algorithm.
Optimal Approach - Tarjan's Bridge-Finding Algorithm
Intuition
To understand Tarjan's algorithm, let's think about what makes an edge a bridge. An edge (u, v) is a bridge if removing it disconnects the graph. But when does removing an edge NOT disconnect the graph? When there is an alternative path between u and v — a detour that doesn't use the direct edge.
Imagine you're exploring a cave system. You start at the entrance and explore deeper, always marking where you came from (this is DFS). Occasionally, you discover a tunnel that loops back to a room you've already visited — this is a back-edge. Back-edges create cycles, and edges within cycles are never bridges because there's always an alternative route.
Here's the critical insight: when we perform DFS and reach a node v from node u (via a tree edge), the edge (u, v) is a bridge if and only if no node in v's subtree has a back-edge reaching u or any ancestor of u. If such a back-edge exists, it provides an alternative path, making the edge (u, v) redundant.
To efficiently detect this, we maintain two values for each node:
- disc[v] (discovery time): When we first visit node v during DFS.
- low[v]: The earliest discovery time reachable from v's subtree (including v itself) through back-edges.
The rule is simple: edge (u, v) is a bridge if low[v] > disc[u]. This means v's entire subtree cannot reach u or any ancestor — there's no back-edge providing an alternative path.
Step-by-Step Explanation
Let's trace through with n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]:
Step 1: Initialize timer = 0. All disc[] and low[] values start as -1 (unvisited). Start DFS from node 0.
Step 2: Visit node 0. Set disc[0] = low[0] = 0. Timer becomes 1. Explore neighbor 1.
Step 3: Visit node 1 (parent = 0). Set disc[1] = low[1] = 1. Timer becomes 2. Explore neighbor 0 — skip, it's the parent. Explore neighbor 2.
Step 4: Visit node 2 (parent = 1). Set disc[2] = low[2] = 2. Timer becomes 3. Explore neighbor 0 — it's already visited and NOT our parent. This is a back-edge! Update low[2] = min(low[2], disc[0]) = min(2, 0) = 0. Explore neighbor 1 — skip, it's the parent.
Step 5: Return to node 1 from node 2. Update low[1] = min(low[1], low[2]) = min(1, 0) = 0. Check bridge condition: low[2] = 0 > disc[1] = 1? No (0 ≤ 1). Edge (1,2) is NOT a bridge. Explore neighbor 3.
Step 6: Visit node 3 (parent = 1). Set disc[3] = low[3] = 3. Timer becomes 4. Node 3 has only neighbor 1, which is the parent — skip. No unvisited neighbors, no back-edges. Return to node 1.
Step 7: Return to node 1 from node 3. Update low[1] = min(low[1], low[3]) = min(0, 3) = 0. Check bridge condition: low[3] = 3 > disc[1] = 1? YES! Edge (1,3) IS a bridge.
Step 8: Return to node 0 from node 1. Update low[0] = min(low[0], low[1]) = min(0, 0) = 0. Check bridge condition: low[1] = 0 > disc[0] = 0? No (0 ≤ 0). Edge (0,1) is NOT a bridge.
Step 9: DFS complete. Result: [[1,3]].
Final values: disc = [0, 1, 2, 3], low = [0, 0, 0, 3]. Node 3's low value (3) exceeds its parent's disc value (1), confirming it cannot reach above node 1 — hence [1,3] is a bridge.
Tarjan's Algorithm — Finding Bridges via DFS Discovery and Low Values — Watch how DFS assigns discovery times and computes low values. When low[v] > disc[u], the edge (u,v) is identified as a bridge.
Algorithm
- Build an adjacency list from the connections.
- Initialize arrays
disc[]andlow[]with -1 (unvisited). Set a global timer to 0. - For each unvisited node, start a DFS.
- In the DFS for node
uwith parentp:
a. Markuas visited. Setdisc[u] = low[u] = timer++.
b. For each neighborvofu:- If
v == p: skip (don't go back to parent). - If
vis not visited: recurse DFS(v, u). After return, updatelow[u] = min(low[u], low[v]). Iflow[v] > disc[u], edge (u, v) is a bridge. - If
vis already visited: it's a back-edge. Updatelow[u] = min(low[u], disc[v]).
- If
- Return the collected bridges.
Code
class Solution {
public:
int timer = 0;
vector<vector<int>> bridges;
void dfs(int u, int parent, vector<vector<int>>& adj,
vector<int>& disc, vector<int>& low) {
disc[u] = low[u] = timer++;
for (int v : adj[u]) {
if (v == parent) {
parent = -1; // skip parent only once
continue;
}
if (disc[v] == -1) {
// Tree edge: v is unvisited
dfs(v, u, adj, disc, low);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) {
bridges.push_back({u, v});
}
} else {
// Back edge: v is already visited
low[u] = min(low[u], disc[v]);
}
}
}
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
vector<vector<int>> adj(n);
for (auto& conn : connections) {
adj[conn[0]].push_back(conn[1]);
adj[conn[1]].push_back(conn[0]);
}
vector<int> disc(n, -1), low(n, -1);
timer = 0;
bridges.clear();
for (int i = 0; i < n; i++) {
if (disc[i] == -1) {
dfs(i, -1, adj, disc, low);
}
}
return bridges;
}
};class Solution:
def criticalConnections(self, n: int, connections: list[list[int]]) -> list[list[int]]:
# Build adjacency list
adj = [[] for _ in range(n)]
for u, v in connections:
adj[u].append(v)
adj[v].append(u)
disc = [-1] * n
low = [-1] * n
timer = [0] # mutable container for closure
bridges = []
def dfs(u: int, parent: int) -> None:
disc[u] = low[u] = timer[0]
timer[0] += 1
for v in adj[u]:
if v == parent:
parent = -1 # skip parent only once
continue
if disc[v] == -1:
# Tree edge
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.append([u, v])
else:
# Back edge
low[u] = min(low[u], disc[v])
for i in range(n):
if disc[i] == -1:
dfs(i, -1)
return bridgesclass Solution {
private int timer = 0;
private List<List<Integer>> bridges = new ArrayList<>();
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (List<Integer> conn : connections) {
adj.get(conn.get(0)).add(conn.get(1));
adj.get(conn.get(1)).add(conn.get(0));
}
int[] disc = new int[n];
int[] low = new int[n];
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
timer = 0;
bridges.clear();
for (int i = 0; i < n; i++) {
if (disc[i] == -1) {
dfs(i, -1, adj, disc, low);
}
}
return bridges;
}
private void dfs(int u, int parent, List<List<Integer>> adj,
int[] disc, int[] low) {
disc[u] = low[u] = timer++;
for (int v : adj.get(u)) {
if (v == parent) {
parent = -1; // skip parent only once
continue;
}
if (disc[v] == -1) {
// Tree edge
dfs(v, u, adj, disc, low);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) {
bridges.add(Arrays.asList(u, v));
}
} else {
// Back edge
low[u] = Math.min(low[u], disc[v]);
}
}
}
}Complexity Analysis
Time Complexity: O(V + E)
We perform a single DFS traversal. Each vertex is visited exactly once (O(V)), and each edge is examined exactly twice — once from each endpoint (O(E)). The disc/low computations and bridge checks at each step are O(1). Total: O(V + E).
For the maximum constraints (V = 10^5, E = 10^5), this is approximately 2 × 10^5 operations — extremely efficient compared to the brute force's 10^10.
Space Complexity: O(V + E)
We store the adjacency list (O(V + E)), the disc[] and low[] arrays (O(V) each), and the DFS recursion stack (O(V) in the worst case for a linear graph). Total: O(V + E).