Critical Connections in a Network — Problem & Solution
Critical Connections in a Network solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Critical Connections in a Network is a hard coding problem on depth-first search, graph and biconnected component, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Graph, Biconnected Component
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n CodeKairo servers numbered 0 … n - 1 are joined by undirected connections, forming one network in which every server can reach every other.
A connection is critical if removing it leaves some server unable to reach some other. Return all critical connections, each written as [smaller, larger], sorted in increasing order.
Example 1
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: The triangle `0-1-2` survives any single removal; the link to server 3 does not.
Example 2
Input: n = 2, connections = [[0,1]]
Output: [[0,1]]
Example 3
Input: n = 3, connections = [[0,1],[1,2],[2,0]]
Output: []
Explanation: A cycle has no critical connection.
Constraints
2 <= n <= 10^5n - 1 <= connections.length <= 10^50 <= connections[i][0], connections[i][1] < nconnections[i][0] != connections[i][1]There are no repeated connections.The answer is returned as [smaller, larger] pairs in increasing order.
Hints for Critical Connections in a Network
Hint 1
A critical connection is a bridge: an edge that lies on no cycle.
Hint 2
Depth-first search and record, for each node, the earliest discovery time reachable from its subtree.
Hint 3
Edge
(p, u)is a bridge exactly when nothing inu's subtree can reach back pastp.
How to solve Critical Connections in a Network
Tarjan's bridge algorithm. During a depth-first search, give each node a discovery time disc and a value low — the earliest discovery time reachable from its subtree using at most one back edge. The tree edge (p, u) is a bridge when low[u] > disc[p].
Approach
- Depth-first search from each unvisited node, stamping
discand initialisinglowto it. - On a tree edge to
v, recurse and thenlow[p] = min(low[p], low[v]). - On a back edge to an already-seen
v,low[u] = min(low[u], disc[v]). - Record
(p, u)whenlow[u] > disc[p], then sort the results.
Why it works
low[u] > disc[p] says nothing under u has a second way back to p or above it, so cutting that edge disconnects the subtree — which is exactly what "critical" means. The one subtlety is skipping the edge you arrived on: skipping by neighbour would wrongly ignore a genuine parallel edge, so the search skips the specific edge index instead. The traversal here is written with an explicit stack because n reaches 100 000 and a path-shaped network would overflow the call stack.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Comparing
low[u]againstlow[p]instead ofdisc[p]misses bridges. - Skipping every edge back to the parent node hides parallel edges; skip the one edge index.
- The back-edge update uses
disc[v], notlow[v].
Reference solution
Python
from typing import List
import sys
def criticalConnections(n: int, connections: List[List[int]]) -> List[List[int]]:
head = [-1] * n
cap = max(1, len(connections) * 2)
nxt = [-1] * cap
to = [0] * cap
ec = 0
for u, v in connections:
to[ec] = v; nxt[ec] = head[u]; head[u] = ec; ec += 1
to[ec] = u; nxt[ec] = head[v]; head[v] = ec; ec += 1
disc = [-1] * n
low = [0] * n
timer = 0
bridges = []
for s in range(n):
if disc[s] >= 0:
continue
disc[s] = low[s] = timer
timer += 1
stack = [(s, -1, head[s])]
while stack:
u, in_edge, e = stack[-1]
if e >= 0:
stack[-1] = (u, in_edge, nxt[e])
if in_edge >= 0 and (e ^ 1) == in_edge:
continue
v = to[e]
if disc[v] < 0:
disc[v] = low[v] = timer
timer += 1
stack.append((v, e, head[v]))
elif disc[v] < low[u]:
low[u] = disc[v]
else:
stack.pop()
if stack:
p = stack[-1][0]
if low[u] < low[p]:
low[p] = low[u]
if low[u] > disc[p]:
bridges.append([min(p, u), max(p, u)])
bridges.sort()
return bridgesJava
public static int[][] criticalConnections(int n, int[][] connections) {
int[] head = new int[n];
Arrays.fill(head, -1);
int cap = Math.max(1, connections.length * 2);
int[] nxt = new int[cap];
int[] to = new int[cap];
int ec = 0;
for (int[] c : connections) {
to[ec] = c[1]; nxt[ec] = head[c[0]]; head[c[0]] = ec; ec++;
to[ec] = c[0]; nxt[ec] = head[c[1]]; head[c[1]] = ec; ec++;
}
int[] disc = new int[n];
int[] low = new int[n];
Arrays.fill(disc, -1);
int timer = 0;
List<int[]> bridges = new ArrayList<>();
int[] stackNode = new int[n + 1];
int[] stackEdge = new int[n + 1];
int[] stackIter = new int[n + 1];
for (int s = 0; s < n; s++) {
if (disc[s] >= 0) continue;
disc[s] = low[s] = timer++;
int top = 0;
stackNode[top] = s;
stackEdge[top] = -1;
stackIter[top] = head[s];
top++;
while (top > 0) {
int u = stackNode[top - 1];
int e = stackIter[top - 1];
if (e >= 0) {
stackIter[top - 1] = nxt[e];
int inEdge = stackEdge[top - 1];
if (inEdge >= 0 && (e ^ 1) == inEdge) continue;
int v = to[e];
if (disc[v] < 0) {
disc[v] = low[v] = timer++;
stackNode[top] = v;
stackEdge[top] = e;
stackIter[top] = head[v];
top++;
} else if (disc[v] < low[u]) {
low[u] = disc[v];
}
} else {
top--;
if (top > 0) {
int p = stackNode[top - 1];
if (low[u] < low[p]) low[p] = low[u];
if (low[u] > disc[p]) {
bridges.add(new int[] { Math.min(p, u), Math.max(p, u) });
}
}
}
}
}
bridges.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
return bridges.toArray(new int[0][]);
}C++
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
vector<int> head(n, -1);
int cap = max(1, (int) connections.size() * 2);
vector<int> nxt(cap, -1), to(cap, 0);
int ec = 0;
for (auto& c : connections) {
to[ec] = c[1]; nxt[ec] = head[c[0]]; head[c[0]] = ec; ec++;
to[ec] = c[0]; nxt[ec] = head[c[1]]; head[c[1]] = ec; ec++;
}
vector<int> disc(n, -1), low(n, 0);
int timer = 0;
vector<vector<int>> bridges;
vector<int> stackNode, stackEdge, stackIter;
for (int s = 0; s < n; s++) {
if (disc[s] >= 0) continue;
disc[s] = low[s] = timer++;
stackNode.push_back(s);
stackEdge.push_back(-1);
stackIter.push_back(head[s]);
while (!stackNode.empty()) {
int u = stackNode.back();
int e = stackIter.back();
if (e >= 0) {
stackIter.back() = nxt[e];
int inEdge = stackEdge.back();
if (inEdge >= 0 && (e ^ 1) == inEdge) continue;
int v = to[e];
if (disc[v] < 0) {
disc[v] = low[v] = timer++;
stackNode.push_back(v);
stackEdge.push_back(e);
stackIter.push_back(head[v]);
} else if (disc[v] < low[u]) {
low[u] = disc[v];
}
} else {
stackNode.pop_back();
stackEdge.pop_back();
stackIter.pop_back();
if (!stackNode.empty()) {
int p = stackNode.back();
if (low[u] < low[p]) low[p] = low[u];
if (low[u] > disc[p]) {
bridges.push_back({ min(p, u), max(p, u) });
}
}
}
}
}
sort(bridges.begin(), bridges.end());
return bridges;
}JavaScript
var criticalConnections = function(n, connections) {
var i;
var head = [];
for (i = 0; i < n; i++) head.push(-1);
var cap = Math.max(1, connections.length * 2);
var nxt = [], to = [];
for (i = 0; i < cap; i++) { nxt.push(-1); to.push(0); }
var ec = 0;
for (i = 0; i < connections.length; i++) {
var u0 = connections[i][0], v0 = connections[i][1];
to[ec] = v0; nxt[ec] = head[u0]; head[u0] = ec; ec++;
to[ec] = u0; nxt[ec] = head[v0]; head[v0] = ec; ec++;
}
var disc = [], low = [];
for (i = 0; i < n; i++) { disc.push(-1); low.push(0); }
var timer = 0;
var bridges = [];
var stackNode = [], stackEdge = [], stackIter = [];
for (var s = 0; s < n; s++) {
if (disc[s] >= 0) continue;
disc[s] = low[s] = timer++;
stackNode.push(s);
stackEdge.push(-1);
stackIter.push(head[s]);
while (stackNode.length > 0) {
var u = stackNode[stackNode.length - 1];
var e = stackIter[stackIter.length - 1];
if (e >= 0) {
stackIter[stackIter.length - 1] = nxt[e];
var inEdge = stackEdge[stackEdge.length - 1];
if (inEdge >= 0 && (e ^ 1) === inEdge) continue;
var v = to[e];
if (disc[v] < 0) {
disc[v] = low[v] = timer++;
stackNode.push(v);
stackEdge.push(e);
stackIter.push(head[v]);
} else if (disc[v] < low[u]) {
low[u] = disc[v];
}
} else {
stackNode.pop();
stackEdge.pop();
stackIter.pop();
if (stackNode.length > 0) {
var p = stackNode[stackNode.length - 1];
if (low[u] < low[p]) low[p] = low[u];
if (low[u] > disc[p]) {
bridges.push([Math.min(p, u), Math.max(p, u)]);
}
}
}
}
}
bridges.sort(function(x, y) { return (x[0] - y[0]) || (x[1] - y[1]); });
return bridges;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure