# Bridges and Low-Link Values

> Find every link whose loss splits a network, in one DFS. Discovery times, low-link values, and the one comparison that decides whether an edge is a bridge.

- Track: DSA (Concepts)
- Level: Intermediate
- Format: Step-through player
- Author: Aayush Ostwal
- Published: 26 October 2026
- Topics: Graphs, DFS, Bridges
- Canonical URL: https://compoundengineer.com/library/dsa/bridges-and-low-link

Concept · Graphs

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

## Why it exists

Prerequisite This lesson builds on depth-first search. If the idea of a DFS and its visited set is new, read Depth-First Search first.

A network of servers is joined by links. Some links are a single point of failure: cut one and the network falls into two pieces that cannot talk to each other. Such a link is a bridge . Other links have a backup, because they sit on a loop.

The direct way to find the bridges is to remove each link in turn and check whether the network is still connected. One check is a DFS, which costs O(V + E). Doing it for all E links costs O(E × (V + E)). With 10⁵ links that is around 2 × 10¹⁰ steps.

Almost all of that work is wasted. Each check walks nearly the same graph again. Can a single DFS tell us which links are bridges?

## The core idea

A link is a bridge exactly when it lies on no loop. So we do not need to remove anything. We only need to know, for each link, whether there is another route between its two ends.

Run one DFS and give every node a discovery time disc : the step at which the DFS first reached it. The links the DFS walks form a tree. In an undirected graph every other link joins a node to one of its ancestors or descendants, so each one is a back edge that climbs up the tree.

Now give every node a second number, low : the earliest discovery time its subtree can reach, using the tree below it and at most one back edge. A back edge that jumps above a tree link is exactly a backup route for it.

A tree link from node down to child is a bridge exactly when low[child] > disc[node] : nothing in the child's subtree climbs back to node or above.

## A worked example

The network has seven nodes. Two loops, 1–2–3 and 4–5–6 , are joined to each other and to node 0 by single links. The DFS starts at node 0. Each node shows disc/low .

Back edge. At node 3, the neighbour 1 was reached earlier and is not where we came from. That is a back edge, so low[3] drops to disc[1] = 1 . The loop 1–2–3 now has a backup, and the number records it.

The pitfall. At node 4 the neighbour 3 is the node we came from. If we counted it, low[4] would become 3 and the link 3–4 would look like it has a backup, when the only "backup" is the link itself. The code skips the parent.

Reporting upward. Node 6 climbs back to node 4, so low[6] = 4 . The value travels up: low[5] = 4 , low[4] = 4 . Back at node 3, the test is low[4] > disc[3] , which is 4 > 3. Nothing below 4 climbs above 4, so 3–4 is a bridge.

The loop passes the test. Coming back from node 2 to node 1, the test is low[2] > disc[1] , which is 1 > 1 and false. Node 2's side reaches node 1 again, so the link 1–2 has a backup. At node 0 the test is 1 > 0, which is true, so 0–1 is a bridge.

## How it works

- When a node is reached, set disc[node] = low[node] = timer and move the timer on.

- For each neighbour nxt:

- nxt is the parent⟶skip it

- nxt is not reached yet⟶go down, then low[node] = min(low[node], low[nxt]), and if low[nxt] > disc[node] the link is a bridge

- nxt is already reached⟶back edge: low[node] = min(low[node], disc[nxt])

### Why it is correct

Take a tree link from node to child . Every route from the child's subtree to the rest of the graph either uses this link or uses a back edge, because tree links only go down and every other link goes up to an ancestor.

If low[child] > disc[node] , no back edge from the subtree lands on node or above. This link is the only way out, so it is a bridge. If low[child] ≤ disc[node] , some back edge lands on node or above. Together with the tree path, that is a loop through the link, so it is not a bridge.

The comparison is strict ( > ) because a back edge that lands exactly on node still makes a loop through node .

## Watch it run

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. The graph shows disc/low beside each node, and a red link is a bridge.

## Complexity

O(V + E)

Time. Here's why: each node 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 adds up to V + 2E steps.

O(V + E)

Space. The adjacency lists hold 2E entries and V lists. disc and low hold V numbers each. The recursion goes as deep as the longest DFS path, up to V. The output holds at most V − 1 bridges.

## Mistakes and variants

- Not skipping the parent. Every tree link then looks like it has a backup and no bridge is found. If the graph can contain two parallel links between the same pair, skip the link you came by (by its index), not every link to the parent: a doubled link is not a bridge.

- Using >= instead of >. That test finds articulation points, the nodes whose removal splits the graph. For those, the root is special: it is an articulation point only if it has two or more DFS children.

- Deep recursion. A graph that is one long path makes the recursion V levels deep. Python stops at about 1000 by default. Use an explicit stack for large inputs.

- Disconnected graphs. Start a DFS from every node that has not been reached. Each start finds the bridges of its own piece.

## Where it shows up

Reach for it when:

- the question is which link, road or dependency is a single point of failure;

- you need to know whether an edge lies on a cycle in an undirected graph;

- brute force would remove each edge and search again.

Problems that use it:

- Critical Connections in a Network

## Interviewer follow-ups

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

"Now find the critical servers instead of the critical links."

What they are checking Whether you understood why the test is > , or only memorised it. If you know the reason, changing the question changes one character.

A strong answer A server is critical (an articulation point) when removing it splits the graph. A back edge that lands exactly on node no longer helps, because node is gone, so the test becomes low[child] >= disc[node] . The root needs a separate rule: it is critical only if it has two or more DFS children.

"What breaks if the network is one path of 10⁶ servers?"

What they are checking Whether you notice that a correct algorithm can still fail in production, and whether you know the fix.

A strong answer The recursion would be 10⁶ calls deep. Python's default limit is around 1000, and other languages can overflow the stack too. Replace the recursion with an explicit stack that holds, for each frame, the node, its parent and the index of the next neighbour. The logic and the O(V + E) cost stay the same.

"Links keep being added. Do we run this again every time?"

What they are checking Whether you ask how often the graph changes before designing anything.

A strong answer For an occasional change, rerunning is fine: O(V + E) is cheap. Say that first, and ask how many changes per second and how large the graph is. If changes are constant, this becomes a different and harder problem, and the answer depends on those numbers.

## Solution code

### Python

```python
class BridgeFinder:
    def findBridges(self, n, connections):
        self.graph = [[] for _ in range(n)]
        for a, b in connections:
            self.graph[a].append(b)
            self.graph[b].append(a)
        self.disc = [-1] * n  # first-reached time
        self.low = [0] * n  # earliest reachable time
        self.bridges = []
        self.timer = 0
        self.dfs(0, -1)
        return self.bridges

    def dfs(self, node, parent):
        self.disc[node] = self.low[node] = self.timer
        self.timer += 1
        for nxt in self.graph[node]:
            if nxt == parent:
                continue  # not a way around
            if self.disc[nxt] == -1:
                self.dfs(nxt, node)
                self.low[node] = min(self.low[node], self.low[nxt])
                if self.low[nxt] > self.disc[node]:
                    self.bridges.append([node, nxt])
            else:
                self.low[node] = min(self.low[node], self.disc[nxt])
`.replace(/^\n/, '');

function solve(n, conns) {
  const g = Array.from({ length: n }, () => []);
  conns.forEach(([a, b]) => { g[a].push(b); g[b].push(a); });
  const disc = Array(n).fill(-1), low = Array(n).fill(0), out = []; let t = 0;
  (function dfs(u, p) {
    disc[u] = low[u] = t++;
    for (const v of g[u]) {
      if (v === p) continue;
      if (disc[v] === -1) { dfs(v, u); low[u] = Math.min(low[u], low[v]); if (low[v] > disc[u]) out.push([u, v]); }
      else low[u] = Math.min(low[u], disc[v]);
    }
  })(0, -1);
  return out;
}
const norm = list => list.map(e => [...e].sort((a, b) => a - b)).sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const sameBridges = (got, exp) => JSON.stringify(norm(got)) === JSON.stringify(norm(exp));

function traceBridges(T, n, connections) {
  const pos = POS[n];
  const nodes = [...Array(n).keys()].map(i => pos ? { id: i, x: pos[i][0], y: pos[i][1] } : { id: i });
  const edges = connections.map(([u, v]) => ({ u, v }));
  const adj = Array.from({ length: n }, () => []);
  connections.forEach(([a, b]) => { adj[a].push(b); adj[b].push(a); });
  const ekey = (a, b) => { const e = edges.find(e => (e.u === a && e.v === b) || (e.u === b && e.v === a)); return `${e.u}-${e.v}
```

---
From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.