Critical Connections in a Network

Hard· Tarjan· Bridges· DFS

Problem

A connected undirected network has n servers and a list of connections. A connection is critical if removing it leaves some servers unable to reach others. Return all critical connections in any order.

Examples

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: [[1,3]]

Edges in the triangle 0-1-2 each have a detour; 1-3 does not.

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

Output: [[0,1]]

Constraints

• 2 <= n <= 10^5
• n - 1 <= connections.length <= 10^5
• No repeated connections

Hints & approach

Hint 1

Critical connections are bridges: edges that lie on no cycle.

Hint 2

During DFS, record the time each node is discovered.

Hint 3

Track the lowest discovery time reachable from a subtree using back edges; if a child cannot reach above its parent, that edge is a bridge.

Approachtry the hints first

Use Tarjan's bridge-finding algorithm. DFS from any node, assigning disc[u] and low[u] as an increasing timestamp. For each neighbour v other than the parent: if v is unvisited, recurse, then set low[u] = min(low[u], low[v]) and report (u, v) as a bridge when low[v] > disc[u]. If v was already visited, it is a back edge, so set low[u] = min(low[u], disc[v]). One DFS finds every bridge.

Time O(V + E) · Space O(V + E)

← PreviousSwim in Rising Water DoneBack to Graphs