cf.completefrontend
GRAPHS · ADVANCED

Bridges and articulation points

Find the edges and nodes whose removal would split an undirected network into pieces, in one DFS using discovery times and low-links.

Time O(n + e)Space O(n + e)2 practice problemsStep-through picture

The idea

In an undirected network, a bridge is an edge that is the only connection between two parts: remove it and the network splits. An articulation point (or cut vertex) is a node with the same property. These are the single points of failure in a network.

Checking each edge by removing it and running a search would take O(e * (n + e)) time. Tarjan's method finds them all in one DFS. Each node gets disc, its discovery time (the order DFS reached it), and low, the earliest discovery time it can reach by going down the DFS tree and then taking at most one edge back up.

The rule: the tree edge from node to its child next is a bridge exactly when low[next] > disc[node]. That means nothing below next has any other way back up to node or above it.

An everyday example

Escape routes from a building

Imagine exploring a building and numbering rooms in the order you enter them. For every room you ask: "from here or any room further in, what's the lowest-numbered room I can reach through a side door?" If all the rooms behind one doorway can't reach anything at or before the room you came from except through that doorway, then that doorway is the only way out. Blocking it traps everyone behind it.

How the example maps to the code
In the exampleIn the code
The number you give a room when you enterdisc[node]
The lowest room reachable through side doors from here or further inlow[node]
The doorway you came throughparentEdge, the edge id you skip
A doorway that is the only way outA bridge: low[next] > disc[node]

From the slow way to bridges and articulation points

  1. Start with the obvious way: remove each edge in turn, run a BFS, and see whether the graph is still in one piece. That's e searches of O(n + e) each. For 10,000 cables, it's hundreds of millions of steps.
  2. Look at what a bridge really is: an edge that lies on no loop. If an edge is on a loop, removing it still leaves the rest of the loop as a way around. So the question becomes: which edges have no loop through them?
  3. DFS on an undirected graph makes loops easy to see. Every edge that isn't a tree edge joins a node to one of its ancestors, called a back edge, because DFS would have explored any unvisited neighbor right away. A back edge from u up to an ancestor closes a loop with the tree path between them. So the tree edge from node to its child next is on a loop exactly when some back edge goes from next's subtree to node or higher.
  4. Number nodes in the order DFS reaches them, disc, and compute low[node]: the smallest disc that node's subtree can reach with one back edge, filled in as each call returns. Then the tree edge is a bridge when low[next] > disc[node]. Skip the edge you came in on by its id, so it isn't mistaken for a back edge. That single DFS is Tarjan's bridge-finding algorithm.

How it works

  1. Build the undirected graph, storing [neighbor, edgeId] so each edge can be recognized from both ends.
  2. Run visit(node, parentEdge) from every node that has no disc yet.
  3. In visit, set disc[node] and low[node] to the current time, then add one to time.
  4. For each [next, id], skip the edge you arrived by (id === parentEdge).
  5. If next is new, visit it, then take low[node] = min(low[node], low[next]). If low[next] > disc[node], the edge is a bridge.
  6. If next was already visited, it's a back edge: take low[node] = min(low[node], disc[next]).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function findBridges(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. edges.forEach(([a, b], id) => {
  4. graph[a].push([b, id]);
  5. graph[b].push([a, id]);
  6. });
  7. const disc = new Array(n).fill(-1);
  8. const low = new Array(n).fill(0);
  9. const bridges = [];
  10. let time = 0;
  11. function visit(node, parentEdge) {
  12. disc[node] = low[node] = time++;
  13. for (const [next, id] of graph[node]) {
  14. if (id === parentEdge) continue;
  15. if (disc[next] === -1) {
  16. visit(next, id);
  17. low[node] = Math.min(low[node], low[next]);
  18. if (low[next] > disc[node]) bridges.push(edges[id]);
  19. } else {
  20. low[node] = Math.min(low[node], disc[next]);
  21. }
  22. }
  23. }
  24. for (let node = 0; node < n; node++) {
  25. if (disc[node] === -1) visit(node, -1);
  26. }
  27. return bridges;
  28. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

One DFS visits each node once and checks each edge from both ends. The graph, disc, low, and the call stack fit in O(n + e).

  • Best caseO(n + e)

    Every input. Even with no edges, the outer loop starts n one-node searches.

  • Average caseO(n + e)

    Every input: each node is visited once and each edge is looked at from both ends.

  • Worst caseO(n + e)

    Every input. A long path is the same speed but makes the recursion n calls deep.

Common mistakes

  • Using low[next] instead of disc[next] for back edges in the articulation point version, which can mark points wrongly.
  • Skipping the parent node instead of the parent edge, which breaks graphs with duplicate edges.
  • Using >= for bridges or > for articulation points. Bridges use low[next] > disc[node]; articulation points use >=.
  • Forgetting the special rule for the DFS root when looking for articulation points.
  • Running it only from node 0 when the network has several pieces.

When to use it

Look for these clues in a problem:

  • The question asks which links or nodes are critical: removing one would disconnect something.
  • The network is undirected, such as cables, roads, or friendships.
  • You need single points of failure, or edges that are not part of any loop.
  • A brute force of removing each edge and testing connectivity would be too slow.

Check yourself

Answer each one in your head first, then open it.

Why is the bridge test > while the articulation point test is >=?

If the child's subtree can reach node itself, there's a loop through the edge, so it's not a bridge. But removing node still cuts that subtree off, so node is a cut point.

Why skip the arrival edge by id instead of skipping the parent node?

With two cables to the parent, the second one is a real way back up. Skipping the parent node would ignore it and report a bridge that isn't one.

How many bridges does a tree with 8 nodes have?

7: a tree has n - 1 edges and no loops, so every edge is a bridge.

In the trace, why is 4-5 not a bridge even though low[5] is not 0?

low[5] = 3, which is above node 4, so 5's subtree can reach node 3 through edge 5-3, around 4-5.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

In a DFS of an undirected graph, every edge is either a tree edge or joins a node to one of its ancestors or descendants. There are no edges across branches: when DFS stands on u and sees an unvisited neighbor v, it visits v right away, so v ends up below u.

When visit(node) returns, low[node] is the smallest disc among node itself and every node reachable from node's subtree by one non-tree edge, not counting the edge node arrived by. The code builds this from node's own visited neighbors, using disc[next], and from each child's low as the child returns. Edges that point down to an already-finished descendant, like 3-5 in the trace, give a larger disc and change nothing.

Removing the tree edge node-next cuts off next's subtree exactly when no other edge leaves that subtree. Because there are no edges across branches, any other edge leaving the subtree must go up to node or higher, which would make low[next] <= disc[node]. So the edge is a bridge exactly when low[next] > disc[node]. Each node is visited once, so the DFS always ends.

Going deeper

3 more ideas

Why the low-link test finds bridges

Everything DFS discovers below next forms a subtree. Its only possible connections to the rest of the graph are the tree edge node-next and back edges from inside the subtree to nodes above it. low[next] is the earliest node those back edges reach. If it's still later than node (low[next] > disc[node]), no back edge escapes, so the tree edge is the only link: a bridge.

Articulation points

A node that isn't the DFS root is an articulation point when some child next has low[next] >= disc[node] (note >=, not >): the child's subtree can reach at most node itself. The root is an articulation point when it has two or more DFS children. In the example, nodes 1 and 3 are articulation points.

Why skip by edge id instead of by parent node

If two cables connect the same pair of nodes, neither is a bridge. Skipping the parent node would ignore the second cable too and wrongly report a bridge. Skipping only the exact edge you came in on handles duplicate edges correctly.

Work it by hand

Every step in a table, with why

Seven nodes: a triangle, a bridge, a second triangle, and a dead-end node. Both bridges are found as the calls return.

n = 7, edges = [[1,0], [0,2], [2,1], [2,3], [3,4], [4,5], [5,3], [5,6]]

StepEventdisc[node]low[node]What happensWhy
1visit(0, -1)00Start the DFSNode 0 is discovered first. Its first neighbor is 1, through edge 0.
2visit(1, 0)11Skip edge 0 back to 0Edge 0 is how node 1 was reached, so it doesn't count as a way back up. Next is node 2, through edge 2.
3visit(2, 2)20Back edge to 0Node 2's edge to 0, edge 1, reaches an already-visited ancestor, so low[2] = disc[0] = 0.
4visit(3, 3)33Go deeperNode 3 is reached by edge 3, from node 2. Its first other neighbor is 4.
5visit(4, 4)44Go deeperNode 4's only other neighbor is 5.
6visit(5, 5)53Back edge to 3Edge 6 joins node 5 to its ancestor 3, so low[5] = 3. Then node 5 visits 6.
7visit(6, 7)66Only the arrival edgeNode 6's one edge is the one it came in on, so low[6] stays at its own disc.
8back at 5 from 6536 > 5: bridge [5, 6]Nothing below 6 can reach 5 or above without edge 7, so it's a bridge.
9back at 4 from 5433 > 4 is falseNode 5's subtree reaches node 3, above 4, so edge 4-5 is on a loop. low[4] becomes 3.
10back at 3 from 4333 > 3 is falseThe subtree reaches node 3 itself, so 3-4 is on the loop 3-4-5. Then node 3's edge to 5 is already visited, and disc[5] = 5 changes nothing.
11back at 2 from 3203 > 2: bridge [2, 3]Nothing below 3 reaches node 2 or higher, so the edge 2-3 is the only link.
12back at 1, then 01, then 00, then 0No more bridgeslow[2] = 0 flows up to 1 and 0, so the triangle's edges are on a loop. Node 0's edge to 2 is already visited.

It returns [[5, 6], [2, 3]], deepest first. The final low is [0, 0, 0, 3, 3, 3, 6]. With the >= rule for articulation points, nodes 2, 3, and 5 are cut points, and the root 0, with one child, is not.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bridges and articulation pointsO(n + e)O(n + e)You need every critical link or node in one pass, on any size of network.
Remove each edge and searchO(n · e + e^2)O(n + e)The graph is tiny, or you want an easy check to test the fast version against.

Extra memory: O(n + e): the adjacency lists store each edge twice, disc and low hold n numbers, and the call stack can be n deep.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bridges and articulation points and the other approaches, on a scale where each line up is 10 times more steps.
  • Bridges and articulation points O(n + e)
  • Remove each edge and search O(n · e + e^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bridges and articulation points202,0002 million
Remove each edge and search2002 million2 trillion

Inputs that need care

6 tricky inputs
Two cables between the same pair: [[0,1], [0,1], [1,2]]
Only the arrival edge is skipped by id, so the second 0-1 counts as a back edge. It returns [[1, 2]], correctly leaving 0-1 out.
A network in several pieces
The outer loop starts a new DFS from every node without a disc, so bridges in every piece are found.
A tree, with no loops
Every edge is a bridge, so it returns all n - 1 edges.
One big loop through every node
Every subtree reaches back to the root, so it returns [].
A self-loop like [3, 3]
It's stored twice in graph[3] and points at an already-visited node, 3 itself, so it changes nothing and is never a bridge.
A path of 100,000 nodes
The recursion goes 100,000 calls deep and can overflow the call stack. Use an explicit stack for graphs that deep.

Variations and follow-ups

Twists interviewers add

Articulation points

Use the same disc and low, but a non-root node is a cut point when some child has low[next] >= disc[node]: the child's subtree can't get above node. The DFS root is a cut point only when it has two or more DFS children.

Two-edge-connected pieces

Remove every bridge, and the pieces left are groups where every pair of nodes has two routes with no shared edge. Shrinking each piece to a node turns the graph into a tree of bridges, which answers "how many bridges lie between a and b?".

Biconnected components

Push each edge onto a stack as DFS explores it. When a child satisfies low[next] >= disc[node], pop edges down to node-next: those edges form one piece that has no single cut point inside.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "critical connections", "single point of failure", "which link, if cut, disconnects the network", or "edges not on any cycle" in an undirected graph.
  • Explain low in plain words: "the earliest node this subtree can climb back to without using the edge it came down". Then the bridge test reads naturally: if the child can't climb back to node, the edge is the only way.
  • Test by hand a triangle with a tail, where only the tail edges are bridges, and a pair of nodes joined by two cables, where neither cable is a bridge.
  • Expect "how do you find articulation points instead?". Answer: change > to >= for non-root nodes, and treat the root separately: it's a cut point only with two or more DFS children.

Where frontend code uses it

The same idea in real UI code
  • Infrastructure and network dashboards that highlight single points of failure, such as the one link between two data centers.
  • Graph visualization tools that highlight edges which, if removed, would split a diagram into separate pieces.
  • Game level editors that check a map for chokepoints: corridors or rooms whose blocking would cut the level in two.

Related algorithms