DSA interview question

Bridges in a Graph (Critical Connections)

Hard · Data structures · Topics: graph, dfs, bridge

The problem

A data-centre network is an undirected graph of servers and links. A link is critical (a bridge) if removing it disconnects part of the network. Find all bridges. Removing each edge and re-checking connectivity is O(E · (V + E)). Tarjan's algorithm finds every bridge in one DFS. It records each vertex's discovery time tin and low, the earliest discovery time reachable from its subtree using one back edge. A tree edge u → v is a bridge exactly when low[v] > tin[u]: nothing in v's subtree can climb back to u or above.

Example: 4 servers, links 0-1, 1-2, 2-0, 1-3 → [[1, 3]].

Function signature

vector<pair<int, int>> criticalConnections(int n, const vector<pair<int, int>>& edges);  // sorted, u < v

Test cases

Input `(n, edges)`	Output (sorted)	Explanation
`(4, [[0,1],[1,2],[2,0],[1,3]])`	`[[1, 3]]`	The triangle has no bridges
`(5, [[0,1],[1,2],[2,0],[1,3],[3,4]])`	`[[1, 3], [3, 4]]`	A path hanging off the cycle
`(6, [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[2,3]])`	`[[2, 3]]`	The link between two triangles
`(3, [[0,1],[1,2],[2,0]])`	`[]`
`(2, [[0,1]])`	`[[0, 1]]`

(Confirm: undirected edges; the graph may be disconnected; each bridge is reported once with its smaller endpoint first.)

How interviewers phrase it

"Return all critical connections in the network: edges that, if removed, will make some server unable to reach another" (LeetCode 1192; GeeksforGeeks "Bridge edge in a graph").

Clarifying questions to ask

Is the graph connected? (Possibly not, so run DFS from every unvisited vertex.)
Can there be parallel edges? (If so, skip only the parent edge's ID, not every edge to the parent vertex.)
What output format? (Any order; sorted here.)

Follow-ups to expect

"What exactly is low[v]?"
"Why low[v] > tin[u] for a bridge?"
"Why skip only the edge we arrived on?"
"How is this related to articulation points?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview