Critical Connections in a Network
Problem
Given n servers connected by undirected edges, return all critical connections — edges whose removal disconnects some server from another. These are exactly the bridges of the graph.
n = 4, edges = [[0,1],[1,2],[2,0],[1,3]][[1,3]]def critical_connections(n, connections):
g = [[] for _ in range(n)]
for u, v in connections:
g[u].append(v); g[v].append(u)
disc = [-1] * n; low = [0] * n
bridges = []; t = [0]
def dfs(u, parent):
disc[u] = low[u] = t[0]; t[0] += 1
for v in g[u]:
if disc[v] == -1:
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.append([u, v])
elif v != parent:
low[u] = min(low[u], disc[v])
for i in range(n):
if disc[i] == -1: dfs(i, -1)
return bridgesfunction criticalConnections(n, connections) {
const g = Array.from({ length: n }, () => []);
for (const [u, v] of connections) { g[u].push(v); g[v].push(u); }
const disc = new Array(n).fill(-1), low = new Array(n).fill(0);
const bridges = []; let t = 0;
function dfs(u, parent) {
disc[u] = low[u] = t++;
for (const v of g[u]) {
if (disc[v] === -1) {
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.push([u, v]);
} else if (v !== parent) {
low[u] = Math.min(low[u], disc[v]);
}
}
}
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
return bridges;
}class Solution {
int[] disc, low; int t = 0;
List<List<Integer>> g; List<List<Integer>> bridges;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> conns) {
g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (var c : conns) { g.get(c.get(0)).add(c.get(1)); g.get(c.get(1)).add(c.get(0)); }
disc = new int[n]; Arrays.fill(disc, -1); low = new int[n]; bridges = new ArrayList<>();
for (int i = 0; i < n; i++) if (disc[i] == -1) dfs(i, -1);
return bridges;
}
void dfs(int u, int parent) {
disc[u] = low[u] = t++;
for (int v : g.get(u)) {
if (disc[v] == -1) {
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > disc[u]) bridges.add(List.of(u, v));
} else if (v != parent) low[u] = Math.min(low[u], disc[v]);
}
}
}class Solution {
vector<vector<int>> g, bridges;
vector<int> disc, low; int t = 0;
void dfs(int u, int parent) {
disc[u] = low[u] = t++;
for (int v : g[u]) {
if (disc[v] == -1) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) bridges.push_back({u, v});
} else if (v != parent) low[u] = min(low[u], disc[v]);
}
}
public:
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& conns) {
g.assign(n, {}); disc.assign(n, -1); low.assign(n, 0);
for (auto& c : conns) { g[c[0]].push_back(c[1]); g[c[1]].push_back(c[0]); }
for (int i = 0; i < n; i++) if (disc[i] == -1) dfs(i, -1);
return bridges;
}
};Explanation
A critical connection is a bridge: an edge whose removal splits the graph. The code finds all of them in a single DFS using Tarjan's algorithm with two numbers per node.
As DFS visits nodes, it stamps each one with a disc time (the order it was first seen). It also computes low[u]: the smallest discovery time reachable from u using tree edges plus at most one back edge. Think of low as "the earliest ancestor I can sneak back to without using the edge I came from".
The bridge test is the line if low[v] > disc[u]. If a child v cannot reach u or anything above u by another route, then the edge (u, v) is the only link holding v's subtree to the rest — so it is a bridge. Back edges update low via min(low[u], disc[v]), but we skip the immediate parent so the edge we arrived on does not count.
Example: graph 0-1, 1-2, 2-0, 1-3. The triangle 0-1-2 lets each node loop back, so low stays small and none of those edges qualify. Node 3 only connects through 1, so low[3] > disc[1] and edge 1-3 is reported as the bridge.
Because the whole thing is one DFS that touches each node and edge once, it finds every bridge efficiently.