Graphs · Bridges

Hard · O(V + E) time · O(V + E) space

Problem

There are n servers numbered from 0 to n - 1, joined by undirected connections. connections[i] = [a, b] is a link between servers a and b. Any server can reach any other, directly or through other servers. A critical connection is a link that, if removed, leaves some server unable to reach another. Return all critical connections, in any order.
Example 1 Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] (servers 0, 1 and 2 form a loop, so only the link to server 3 is critical. [[3,1]] is also accepted.)
Example 2 Input: n = 2, connections = [[0,1]] Output: [[0,1]] (the only link is critical)
Constraints 2 ≤ n ≤ 10^5 n - 1 ≤ connections.length ≤ 10^5 0 ≤ a, b ≤ n - 1, a ≠ b No two connections are the same.

Brute force

This problem has three requirements:

  1. A link is critical if removing it leaves some pair of servers unable to reach each other.
  2. Return every critical link, in any order.
  3. The network starts out connected, so any split is caused by the removed link.

So the question for each link is: without it, is there still another route between its two ends? If yes, the link sits on a loop and is safe. If no, it is critical. Here are two links on the same network.

The direct approach removes each link in turn and checks whether the network is still connected.

The problem with it

Each check is a DFS that costs O(V + E), and there are E links, so the total is O(E × (V + E)). With 10⁵ links and 10⁵ servers that is around 2 × 10¹⁰ steps, far too slow.

It is also wasteful. Every check walks almost the same graph again, only to learn whether one link had a backup. A link that sits on a loop gets re-proved safe once for every other link we test around it.

How to think your way to the optimal solution

The brute force asks "is there another route?" once per link, and each answer costs a full search. So can one DFS answer that question for every link at once?

Run a single DFS and look at what it builds. The links it walks form a tree. In an undirected graph, every other link joins a server to one of its ancestors or descendants, so it climbs back up the tree. For a tree link from node down to child, a backup route exists only if something in the child's subtree has a link that climbs back to node or above. Otherwise this link is the only way between the subtree and the rest.

That turns the question into a number. Stamp each server with the time the DFS reached it, disc. Then for each server record low: the earliest stamp its subtree can reach with one climbing link. The test for a tree link is now one comparison, low[child] > disc[node].

The optimal solution

Prerequisite

This solution is the bridge-finding algorithm. This page uses it; Bridges and Low-Link Values teaches it from scratch, with a different example and the proof that the test is correct. Read it first if disc and low are new to you.

  1. When a server is reached, set disc[node] = low[node] = timer and move the timer on.
  2. nxt is the parent⟶skip it
  3. nxt is not reached yet⟶go down, then low[node] = min(low[node], low[nxt]). If low[nxt] > disc[node], the link is critical.
  4. nxt is already reached⟶low[node] = min(low[node], disc[nxt])
  5. Start at server 0, which reaches every server because the network is connected, and return the critical links.

Pick an input, then press Play or use the arrow keys. The highlighted line is the one running, the number beside each line counts how often it ran, and the dashed box shows the comparison and what it decides. Each node shows disc/low, and a red link is critical.

Complexity analysis

ApproachTimeSpace
Remove each link and searchO(E × (V + E))O(V + E)
One DFS with disc and lowO(V + E)O(V + E)
O(V + E)
Time. Here's why: each server is entered once, so the DFS makes V calls. Each link is looked at twice, once from each end, for O(1) work each. That is V + 2E steps in total.
O(V + E)
Space. The adjacency lists hold V lists and 2E entries, and disc and low hold V numbers each. The recursion is as deep as the longest DFS path, up to V. The output holds at most V − 1 links and is counted separately.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Could Union-Find do this instead?"

What they are checkingWhether you considered other tools for "is this edge on a cycle", and can say why you picked DFS.

A strong answerUnion-Find tells you that the edge you are adding closes a loop, but not which earlier edges lie on that loop. Marking those needs the path between the two ends, which means walking the graph anyway. DFS with low gets every bridge in one pass, so I would use it.

"The network is one chain of 10⁵ servers. Does your code run?"

What they are checkingWhether you noticed that the constraint allows a DFS 10⁵ levels deep.

A strong answerNot in Python as written: the default recursion limit is about 1000, and a chain would hit it. Other languages can overflow the call stack too. I would switch to an explicit stack that keeps, for each frame, the node, its parent and the index of the next neighbour. The logic and the O(V + E) cost do not change.

"Could the network have two links between the same pair of servers?"

What they are checkingWhether you know what the parent check really assumes.

A strong answerThe problem says no two connections are the same, so skipping the parent node is safe. With a doubled link, neither copy is critical, because each is a backup for the other. Skipping by parent node would wrongly skip both. I would skip only the one link I arrived by, using its index.

Spot this pattern