Appearance
4.19.4 — Fragile Links: Bridges & Articulation Points
A delivery company has seven warehouses joined by two-way roads. Before the monsoon, the operations team asks two questions. Which single road, if it floods, cuts some warehouses off from the rest? And which single warehouse, if it closes, splits the network? In the map below, the answers are the road between warehouses 1 and 3, the road between 4 and 6, and the warehouses 1, 3 and 4.
Those roads are called bridges: edges whose removal increases the number of connected pieces of an undirected graph. Those warehouses are articulation points (also called cut vertices): vertices whose removal does the same. Both questions show up wherever a network must survive one failure: data-centre links, power grids, road planning, and the LeetCode problem "Critical Connections in a Network".
The brute force, and its waste
Remove each road in turn and run a BFS (4.19.1) to see whether everything is still reachable. That is E searches of O(V + E) each, so O(E(V + E)). For 10^5 roads that is about 2 \times 10^{10} steps. The waste: every search rediscovers the whole network from scratch, although removing one road changes almost nothing. One DFS already contains enough information to answer for every road at once.
The idea: how high can a subtree climb back?
Run one depth-first search and write down, for each warehouse, the order in which it was first reached: its discovery time disc. The roads the DFS travels form a tree. Every other road connects a warehouse to one of its ancestors in that tree, a back edge (in an undirected DFS there are no other kinds, because DFS would have travelled any road leading to an unvisited warehouse).
Now ask, for each warehouse v: using roads inside the part of the tree below v, plus at most one back edge, what is the earliest-discovered warehouse I can reach? That number is low[v], the low-link value.
The whole algorithm rests on one consequence:
- The tree road from parent
udown to childvis a bridge exactly whenlow[v] > disc[u]. Everything belowvcannot get back touor above without using that road, so cutting it strands them. - A non-root warehouse
uis an articulation point exactly when it has a childvwithlow[v] >= disc[u]. Everything belowvcan reachuat best, never above it, so removingustrands them. - The root of the DFS is an articulation point exactly when it has two or more children in the DFS tree. Two separate subtrees hanging from the root can only meet through the root, because a back edge between them would have made one a descendant of the other.
The figure shows the seven warehouses, each labelled with its disc and low from a DFS that starts at warehouse 0.
disc / low. Warehouse 2 can climb back to 0 through its back edge, so the whole left triangle has low 0. Warehouses 3, 4 and 5 can climb only to 3, so nothing below warehouse 1 can get back above it without the road 1–3.Read the two bridges off the labels. The road from 1 down to 3: low[3] = 3 is greater than disc[1] = 1, so it is a bridge. The road from 4 down to 6: low[6] = 6 > disc[4] = 4, a bridge. The road from 3 down to 4 is not: low[4] = 3 is not greater than disc[3] = 3, because warehouse 5's back edge reaches 3.
The solution
python
import sys
def fragile_links(n: int, roads: list[tuple[int, int]]) -> tuple[list[tuple[int, int]], list[int]]:
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for i, (a, b) in enumerate(roads): # (1)
adj[a].append((b, i))
adj[b].append((a, i))
disc = [-1] * n # (2) discovery time, -1 = unvisited
low = [0] * n # (3)
bridges: list[tuple[int, int]] = []
cut_points: set[int] = set()
clock = 0
def dfs(u: int, came_by: int) -> None:
nonlocal clock
disc[u] = low[u] = clock
clock += 1
children = 0
for v, edge in adj[u]:
if edge == came_by: # (4) skip only the road we arrived on
continue
if disc[v] == -1: # tree edge: explore v
children += 1
dfs(v, edge)
low[u] = min(low[u], low[v]) # (5)
if low[v] > disc[u]: # (6) v's side cannot get back above u
bridges.append((u, v))
if came_by != -1 and low[v] >= disc[u]: # (7)
cut_points.add(u)
else: # back edge to an ancestor
low[u] = min(low[u], disc[v]) # (8)
if came_by == -1 and children >= 2: # (9) the root is special
cut_points.add(u)
sys.setrecursionlimit(max(1000, 2 * n + 10))
for s in range(n):
if disc[s] == -1:
dfs(s, -1)
return bridges, sorted(cut_points)
if __name__ == "__main__":
roads = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (4, 6)]
print(fragile_links(7, roads)) # → ([(4, 6), (1, 3)], [1, 3, 4])ts
function fragileLinks(n: number, roads: [number, number][]): { bridges: [number, number][]; cutPoints: number[] } {
const adj: [number, number][][] = Array.from({ length: n }, () => []);
roads.forEach(([a, b], i) => { adj[a].push([b, i]); adj[b].push([a, i]); }); // (1)
const disc = new Array<number>(n).fill(-1); // (2)
const low = new Array<number>(n).fill(0); // (3)
const bridges: [number, number][] = [];
const cutPoints = new Set<number>();
let clock = 0;
const dfs = (u: number, cameBy: number): void => {
disc[u] = low[u] = clock++;
let children = 0;
for (const [v, edge] of adj[u]) {
if (edge === cameBy) continue; // (4)
if (disc[v] === -1) {
children++;
dfs(v, edge);
low[u] = Math.min(low[u], low[v]); // (5)
if (low[v] > disc[u]) bridges.push([u, v]); // (6)
if (cameBy !== -1 && low[v] >= disc[u]) cutPoints.add(u); // (7)
} else {
low[u] = Math.min(low[u], disc[v]); // (8)
}
}
if (cameBy === -1 && children >= 2) cutPoints.add(u); // (9)
};
for (let s = 0; s < n; s++) if (disc[s] === -1) dfs(s, -1);
return { bridges, cutPoints: [...cutPoints].sort((a, b) => a - b) };
}
const roads: [number, number][] = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3], [4, 6]];
console.log(JSON.stringify(fragileLinks(7, roads))); // → {"bridges":[[4,6],[1,3]],"cutPoints":[1,3,4]}- Each road is stored in both directions with its index, so the DFS can tell "the road I came in on" apart from "another road to the same place".
disc[u]is whenuwas first reached, and doubles as the visited marker.low[u]starts asdisc[u]and can only go down as the search discovers better ways back up.- Skip the road you arrived on, not the warehouse you came from. If two parallel roads join the same pair of warehouses, the second one is a genuine way back, and neither road is a bridge. Skipping by vertex would ignore the second road and wrongly report a bridge. Skipping by edge index handles it.
- After the child's subtree is finished, anything it could reach,
ucan reach too. - The bridge test from the idea section.
- The articulation test for a non-root warehouse. Note
>=here against>in line (6): if the subtree can reachuitself but nothing above, the road is not a bridge (there is another way tou), but removing the warehouseustill strands the subtree. - A back edge to an already-discovered warehouse lets
uclimb straight to it. - The root has nothing above it, so line (7)'s test does not apply; it is a cut point only if the DFS left it more than once to find unvisited warehouses.
The program prints ([(4, 6), (1, 3)], [1, 3, 4]) in Python and {"bridges":[[4,6],[1,3]],"cutPoints":[1,3,4]} in TypeScript. The Python version was also checked against the brute force on 3,000 random small networks, including networks with parallel roads, and agreed on every bridge and every cut point.
Hand trace
The DFS starts at 0 and visits neighbours in the order the roads were listed.
| Step | At | Event | Result |
|---|---|---|---|
| 1 | 0 | discovered | disc = low = 0 |
| 2 | 1 | discovered from 0 | disc = low = 1 |
| 3 | 2 | discovered from 1 | disc = low = 2 |
| 4 | 2 | back edge to 0 | low[2] = 0 |
| 5 | 1 | child 2 finished | low[1] = 0; low[2] = 0 not > 1, no bridge |
| 6 | 3 | discovered from 1 | disc = low = 3 |
| 7 | 4 | discovered from 3 | disc = low = 4 |
| 8 | 5 | discovered from 4 | disc = low = 5 |
| 9 | 5 | back edge to 3 | low[5] = 3 |
| 10 | 4 | child 5 finished | low[4] = 3; 3 not > 4 |
| 11 | 6 | discovered from 4 | disc = low = 6, no other roads |
| 12 | 4 | child 6 finished | 6 > 4: bridge 4–6; 6 ≥ 4: 4 is a cut point |
| 13 | 3 | child 4 finished | low[3] stays 3; 3 ≥ 3: 3 is a cut point |
| 14 | 1 | child 3 finished | 3 > 1: bridge 1–3; 3 ≥ 1: 1 is a cut point |
| 15 | 0 | done | root with one child: not a cut point |
When the network is deep: the explicit-stack version
Recursion depth equals the length of the longest path the DFS walks, which can be every warehouse in a long chain. Measured here: the Python version above handled a chain of 100,000 warehouses on Python 3.14 (since Python 3.12, deep Python-to-Python recursion no longer consumes the C stack, so raising the recursion limit is enough). The recursive TypeScript version ran out of stack on a chain of just 5,000 (RangeError: Maximum call stack size exceeded), because Node.js gives JavaScript under a megabyte of stack by default. For large inputs in TypeScript, keep the recursion in an array:
ts
function fragileLinksIterative(n: number, roads: [number, number][]): { bridges: [number, number][]; cutPoints: number[] } {
const adj: [number, number][][] = Array.from({ length: n }, () => []);
roads.forEach(([a, b], i) => { adj[a].push([b, i]); adj[b].push([a, i]); });
const disc = new Array<number>(n).fill(-1);
const low = new Array<number>(n).fill(0);
const next = new Array<number>(n).fill(0); // (a) how far through adj[u] we have got
const cameBy = new Array<number>(n).fill(-1);
const parent = new Array<number>(n).fill(-1);
const children = new Array<number>(n).fill(0);
const bridges: [number, number][] = [];
const cutPoints = new Set<number>();
let clock = 0;
for (let s = 0; s < n; s++) {
if (disc[s] !== -1) continue;
disc[s] = low[s] = clock++;
const stack = [s]; // (b) the recursion, made explicit
while (stack.length > 0) {
const u = stack[stack.length - 1];
if (next[u] < adj[u].length) {
const [v, edge] = adj[u][next[u]++];
if (edge === cameBy[u]) continue;
if (disc[v] === -1) { // (c) "call" dfs(v)
parent[v] = u; cameBy[v] = edge; children[u]++;
disc[v] = low[v] = clock++;
stack.push(v);
} else {
low[u] = Math.min(low[u], disc[v]);
}
} else { // (d) u is finished: "return" to its parent
stack.pop();
const p = parent[u];
if (p !== -1) {
low[p] = Math.min(low[p], low[u]);
if (low[u] > disc[p]) bridges.push([p, u]);
if (parent[p] !== -1 && low[u] >= disc[p]) cutPoints.add(p);
} else if (children[u] >= 2) {
cutPoints.add(u);
}
}
}
}
return { bridges, cutPoints: [...cutPoints].sort((a, b) => a - b) };
}- (a) For each warehouse, how far through its list of roads the search has got. This replaces the loop position a recursive call would remember for you.
- (b) The stack holds the warehouses whose recursive call would still be in progress, deepest on top.
- (c) Finding an unvisited neighbour is the "call": set it up exactly as the recursive version would on entry, and push it.
- (d) When a warehouse has no roads left to examine, its "call" returns: pop it and do the work the recursive version does after
dfs(v)returns (lines 5 to 7), now on the parent.
It produced the same answer as the recursive version on 3,000 random networks, and handled the 100,000-warehouse chain (99,999 bridges, 99,998 cut points, as a chain should have).
Complexity
Time: O(V + E). Every warehouse is discovered once. Every road is examined twice, once from each end, and each examination is constant work: a comparison, perhaps a min. The bridge and cut-point tests run once per tree road, when the child finishes. There is one DFS, not one per road, which is the whole improvement over O(E(V + E)).
Space: O(V + E) for the adjacency lists, plus O(V) for disc, low and the recursion or explicit stack.
Edge cases
- A disconnected network: the outer loop starts a fresh DFS in every piece, and each start is a root.
- Parallel roads between the same pair: never bridges, handled by skipping by edge index.
- Self-loops (a road from a warehouse to itself): cannot be bridges and never change
low; the tests above dropped them, and the algorithm tolerates them. - A single warehouse, or two joined by one road: no cut points; in the second case that one road is a bridge.
Variations you will meet
- Critical Connections in a Network (LeetCode 1192) is the bridges half of this page, exactly.
- Directed graphs ask a different question, which groups can all reach each other, answered by strongly connected components in 4.19.2. Tarjan's SCC algorithm uses the same
disc/lowidea. - Biconnected components are the pieces that remain connected after removing any single warehouse; they fall out of the same DFS by collecting edges on a stack and popping a component whenever the articulation test succeeds.
- "Is the network safe against any single road failure?" is "are there zero bridges?", which is the question a network engineer actually asks.
The generalisation: one DFS, two numbers per vertex (when it was found, how high its subtree can climb back), answers every single-failure question about an undirected graph in linear time.
What the interviewer will push on
"What does low-link actually mean?" They are checking whether you can say it in a sentence: the earliest-discovered vertex reachable from this vertex's subtree using tree edges downward and at most one back edge. A memorised answer recites the update rule; a real one explains why low[v] > disc[u] means "the subtree is stranded".
"Why > for bridges but >= for articulation points?" If the subtree can climb back to exactly u, there is a second route to u, so the road is not a bridge, but removing u itself still cuts the subtree off. Getting this distinction right is the clearest signal.
"Why is the root handled separately?" Nothing is above the root, so the subtree test is meaningless there; instead, two or more DFS children prove the root is the only connection between them.
"What about parallel edges?" Skipping the parent vertex reports false bridges on duplicate roads. Skipping the arrival edge is correct. Candidates who know this have usually been bitten by it.
"Your solution overflowed the stack on the big test. Why?" Recursion depth can equal the number of vertices on a long chain. The fix is the explicit-stack version, or, in Python 3.12 and later, a raised recursion limit. Saying which applies to your language is the strong answer.
One thing to volunteer: bridges are the reason redundant networks are designed as rings or meshes rather than trees. A tree network is all bridges: every link is a single point of failure. Connecting the problem to that design rule shows you see where the algorithm is used.
Recall
- A bridge is an edge whose removal disconnects the graph; an articulation point is such a vertex. Both come from one DFS in O(V + E).
disc[v]is discovery order;low[v]is the earliest-discovered vertexv's subtree can reach using at most one back edge.- Tree edge
u → vis a bridge ifflow[v] > disc[u]; non-rootuis a cut point iff some child haslow[v] >= disc[u]; the root is a cut point iff it has 2 or more DFS children. - Skip the edge you arrived on, not the parent vertex, or parallel edges become false bridges.
- Recursion depth can reach V: the recursive TypeScript version overflowed at a 5,000-node chain, so large inputs need the explicit-stack version.
Self-test: Compute disc and low for a square of four vertices with one diagonal, and say why there are no bridges · Why > for bridges and >= for cut points? · Why can the root not use the subtree test? · Construct two parallel roads where skipping by vertex reports a false bridge · Where does the explicit stack store what a recursive call would remember?
Next: 4.20 is the graph problem set — thirteen problems, and nearly all of them are one of three things: flood fill on a grid, breadth-first search for a shortest path, or a topological sort over dependencies.