Critical Connections in a Network

Problem

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.

Examples

Example 1:

graph LR
	A[1] --- B[2] --- C[0]
	C --- A
	A ---|Critical| 3:::Critical

linkStyle 3 stroke:red,stroke-width:4px

1
2
3
4
5


Input:
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output:
 [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

1
2
3
4


Input:
n = 2, connections = [[0,1]]
Output:
 [[0,1]]

Solution

Method 1 – Tarjan’s Algorithm for Bridges

Intuition

A critical connection (bridge) is an edge whose removal increases the number of connected components in the graph. Tarjan’s algorithm allows us to efficiently find all such bridges using DFS and tracking discovery and low-link times.

Approach

Build the Graph: Construct an undirected graph from the given connections list, where each server is a node and each connection is an undirected edge.
DFS Traversal with Discovery and Low-Link Times: Use Depth-First Search (DFS) to traverse the graph. For each node, assign a discoveryTime (the time when the node is first visited) and a lowTime (the earliest discovered node reachable from the current node, including itself and its descendants). These are tracked using arrays like disc and low (or similar names in code).
Parent Check in DFS: When iterating over neighbors in DFS, we skip the parent node (the node we came from). This is crucial because if we allowed the parent to update the lowTime of the current node, it would always be less than or equal to the current node’s discoveryTime, causing every edge to be incorrectly marked as a bridge. By skipping the parent, we ensure only true back-edges and child-edges are considered. (See Q1)
Visited Array Optimization: We do not need a separate visited[] array. If lowTime[i] == 0 (or disc[i] == -1 depending on initialization), then node i has not been visited yet. This saves memory and simplifies the code. (See Q2)
Timer Variable: The timer can be a simple integer or an array with one value (e.g., [0] in Python). Using an array allows the timer to be mutable within nested functions, but a single integer works as well in most languages. (See Q3)
Identifying Bridges: After visiting a neighbor v from node u, if low[v] > disc[u], then the edge (u, v) is a critical connection (bridge). This means that there is no back-edge from the subtree rooted at v to any ancestor of u, so removing (u, v) would disconnect the graph. (See Q5)
Preserving Input Order (Optional): Since the graph is undirected, the order of nodes in each connection does not matter. However, if you want to preserve the order as in the input, you can use a hash set to store the original connections. When adding a bridge to the result, check if it exists in the set in the same order; if not, reverse it. This ensures the output matches the input order where possible. (See Q4)

Summary of Key Points:

Always skip the parent node in DFS to avoid false bridges.
You can avoid a visited[] array by checking the initialization value of disc or low.
The timer can be managed as an integer or a mutable array, depending on language and style.
To preserve input order, use a set or map to check the original direction of each connection.
A bridge is found when low[neighbor] > disc[current] after DFS.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <vector>
using namespace std;
class Solution {
public:
	vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
		vector<vector<int>> g(n), res;
		for (auto& e : connections) {
			g[e[0]].push_back(e[1]);
			g[e[1]].push_back(e[0]);
		}
		vector<int> disc(n, -1), low(n, -1);
		int time = 0;
		function<void(int,int)> dfs = [&](int u, int p) {
			disc[u] = low[u] = time++;
			for (int v : g[u]) {
				if (v == p) continue;
				if (disc[v] == -1) {
					dfs(v, u);
					low[u] = min(low[u], low[v]);
					if (low[v] > disc[u]) res.push_back({u, v});
				} else {
					low[u] = min(low[u], disc[v]);
				}
			}
		};
		for (int i = 0; i < n; ++i) if (disc[i] == -1) dfs(i, -1);
		return res;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func criticalConnections(n int, connections [][]int) [][]int {
	g := make([][]int, n)
	for _, e := range connections {
		g[e[0]] = append(g[e[0]], e[1])
		g[e[1]] = append(g[e[1]], e[0])
	}
	disc := make([]int, n)
	low := make([]int, n)
	for i := range disc { disc[i] = -1 }
	var res [][]int
	time := 0
	var dfs func(u, p int)
	dfs = func(u, p int) {
		disc[u], low[u] = time, time; time++
		for _, v := range g[u] {
			if v == p { continue }
			if disc[v] == -1 {
				dfs(v, u)
				low[u] = min(low[u], low[v])
				if low[v] > disc[u] { res = append(res, []int{u, v}) }
			} else {
				low[u] = min(low[u], disc[v])
			}
		}
	}
	for i := 0; i < n; i++ { if disc[i] == -1 { dfs(i, -1) } }
	return res
}
func min(a, b int) int { if a < b { return a }; return b }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import java.util.*;
class Solution {
	int time = 0;
	public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
		List<Integer>[] graph = new List[n];
		for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
		for (List<Integer> e : connections) {
			graph[e.get(0)].add(e.get(1));
			graph[e.get(1)].add(e.get(0));
		}
		List<List<Integer>> ans = new ArrayList<>();
		int[] disc = new int[n], low = new int[n];
		Arrays.fill(disc, -1);
		for (int i = 0; i < n; i++)
			if (disc[i] == -1) dfs(graph, i, -1, disc, low, ans);
		return ans;
	}
	private void dfs(List<Integer>[] graph, int u, int parent, int[] disc, int[] low, List<List<Integer>> ans) {
		disc[u] = low[u] = time++;
		for (int v : graph[u]) {
			if (v == parent) continue;
			if (disc[v] == -1) {
				dfs(graph, v, u, disc, low, ans);
				low[u] = Math.min(low[u], low[v]);
				if (low[v] > disc[u]) ans.add(Arrays.asList(u, v));
			} else {
				low[u] = Math.min(low[u], disc[v]);
			}
		}
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
	var time = 0
	fun criticalConnections(n: Int, connections: List<List<Int>>): List<List<Int>> {
		val g = Array(n) { mutableListOf<Int>() }
		for (e in connections) {
			g[e[0]].add(e[1]); g[e[1]].add(e[0])
		}
		val disc = IntArray(n) { -1 }
		val low = IntArray(n)
		val ans = mutableListOf<List<Int>>()
		fun dfs(u: Int, parent: Int) {
			disc[u] = time; low[u] = time; time++
			for (v in g[u]) {
				if (v == parent) continue
				if (disc[v] == -1) {
					dfs(v, u)
					low[u] = minOf(low[u], low[v])
					if (low[v] > disc[u]) ans.add(listOf(u, v))
				} else {
					low[u] = minOf(low[u], disc[v])
				}
			}
		}
		for (i in 0 until n) if (disc[i] == -1) dfs(i, -1)
		return ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
	def criticalConnections(self, n: int, connections: list[list[int]]) -> list[list[int]]:
		g = [[] for _ in range(n)]
		for u, v in connections:
			g[u].append(v); g[v].append(u)
		disc = [-1]*n; low = [0]*n; time = [0]; ans = []
		def dfs(u, parent):
			disc[u] = low[u] = time[0]; time[0] += 1
			for v in g[u]:
				if v == parent: continue
				if disc[v] == -1:
					dfs(v, u)
					low[u] = min(low[u], low[v])
					if low[v] > disc[u]: ans.append([u, v])
				else:
					low[u] = min(low[u], disc[v])
		for i in range(n):
			if disc[i] == -1: dfs(i, -1)
		return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


impl Solution {
	pub fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
		let n = n as usize;
		let mut g = vec![vec![]; n];
		for e in &connections {
			g[e[0] as usize].push(e[1] as usize);
			g[e[1] as usize].push(e[0] as usize);
		}
		let mut disc = vec![-1; n];
		let mut low = vec![0; n];
		let mut time = 0;
		let mut ans = vec![];
		fn dfs(u: usize, parent: isize, g: &Vec<Vec<usize>>, disc: &mut Vec<i32>, low: &mut Vec<i32>, time: &mut i32, ans: &mut Vec<Vec<i32>>) {
			disc[u] = *time; low[u] = *time; *time += 1;
			for &v in &g[u] {
				if v as isize == parent { continue; }
				if disc[v] == -1 {
					dfs(v, u as isize, g, disc, low, time, ans);
					low[u] = low[u].min(low[v]);
					if low[v] > disc[u] { ans.push(vec![u as i32, v as i32]); }
				} else {
					low[u] = low[u].min(disc[v]);
				}
			}
		}
		for i in 0..n {
			if disc[i] == -1 {
				dfs(i, -1, &g, &mut disc, &mut low, &mut time, &mut ans);
			}
		}
		ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


function criticalConnections(n: number, connections: number[][]): number[][] {
	const g: number[][] = Array.from({length: n}, () => []);
	for (const [u, v] of connections) {
		g[u].push(v); g[v].push(u);
	}
	const disc = Array(n).fill(-1), low = Array(n).fill(0);
	let time = 0;
	const ans: number[][] = [];
	function dfs(u: number, parent: number) {
		disc[u] = low[u] = time++;
		for (const v of g[u]) {
			if (v === parent) continue;
			if (disc[v] === -1) {
				dfs(v, u);
				low[u] = Math.min(low[u], low[v]);
				if (low[v] > disc[u]) ans.push([u, v]);
			} else {
				low[u] = Math.min(low[u], disc[v]);
			}
		}
	}
	for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
	return ans;
}

Complexity

⏰ Time complexity: O(N + E) where N is the number of nodes and E is the number of edges (DFS traversal).
🧺 Space complexity: O(N + E) for the graph and auxiliary arrays.

Problem#

Examples#

Solution#

Method 1 – Tarjan’s Algorithm for Bridges#

Intuition#

Approach#

Code#

Complexity#