DSA Tracker

Visualize

Critical Connections in a Network

Tarjan's DFS: an edge is a bridge only if nothing in the child's subtree can reach back past it

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

A single DFS pass answers this without ever actually removing an edge. Give every node a discovery time, then track its low-link: the earliest discovery time reachable from that node's subtree using at most one back-edge. When a child's low-link can only reach back down to itself or later — never past its parent's own discovery time — the tree edge connecting them is the ONLY way between the two halves it separates, so removing it disconnects the graph. Any edge that sits on a cycle always has a back-edge shortcut lowering some descendant's low-link past the parent, so it survives.

Details

Animated on: 7 nodes, undirected: two triangles (0-1-2 and 3-4-5) joined by edge (2,3), plus a pendant leaf 6 hanging off 5 — which edges are bridges?

Problem:Critical Connections in a NetworkHard

Tarjan's DFS: an edge is a bridge only if nothing in the child's subtree can reach back past it

step 1 / 16

Badge = discovery time / lowest reachable time

Call stack

0

Start the DFS at node 0: give it discovery time 0 and set its low-link to the same value — the low-link only ever drops from here, never rises.

Pseudocode
1FUNCTION findBridges(n, edges):
2  BUILD adj FROM edges
3  tin, low <- ARRAY OF n VALUES -1
4  timer <- 0
5  FUNCTION dfs(u, parent):
6    tin[u], low[u] <- timer
7    timer <- timer + 1
8    FOR EACH v IN adj[u]
9      IF v = parent CONTINUE
10      ELSE IF tin[v] = -1
11        dfs(v, u)
12        low[u] <- MIN(low[u], low[v])
13        IF low[v] > tin[u]
14          APPEND (u, v) TO bridges
15      ELSE
16        low[u] <- MIN(low[u], tin[v])
17  dfs(0, -1)
18  RETURN bridges

← / → step · space play · Home restart

Every step in words

Show all 16 steps
  1. Start the DFS at node 0: give it discovery time 0 and set its low-link to the same value — the low-link only ever drops from here, never rises.
  2. Descend into node 1 from 0: discovery time 1, low-link 1. Every node on the current call stack (0, 1) is an ancestor that 1 could still report a shortcut back to.
  3. Descend into node 2 from 1: discovery time 2, low-link 2. Every node on the current call stack (0, 1, 2) is an ancestor that 2 could still report a shortcut back to.
  4. Node 2 also reaches already-visited node 0 directly — a back-edge, not a tree edge. 0 was discovered at time 0, earlier than 2, so 2's low-link drops to 0: there is a shortcut from here straight up to an ancestor, skipping the tree path entirely.
  5. Descend into node 3 from 2: discovery time 3, low-link 3. Every node on the current call stack (0, 1, 2, 3) is an ancestor that 3 could still report a shortcut back to.
  6. Descend into node 4 from 3: discovery time 4, low-link 4. Every node on the current call stack (0, 1, 2, 3, 4) is an ancestor that 4 could still report a shortcut back to.
  7. Descend into node 5 from 4: discovery time 5, low-link 5. Every node on the current call stack (0, 1, 2, 3, 4, 5) is an ancestor that 5 could still report a shortcut back to.
  8. Node 5 also reaches already-visited node 3 directly — a back-edge, not a tree edge. 3 was discovered at time 3, earlier than 5, so 5's low-link drops to 3: there is a shortcut from here straight up to an ancestor, skipping the tree path entirely.
  9. Descend into node 6 from 5: discovery time 6, low-link 6. Every node on the current call stack (0, 1, 2, 3, 4, 5, 6) is an ancestor that 6 could still report a shortcut back to.
  10. Back from 6: its low-link is 6, which is HIGHER than 5's own discovery time 5 — nothing in 6's subtree can reach 5 or anything above it any other way. Edge (5, 6) is a bridge.
  11. Back from 5: its low-link 3 reaches at or before 4's discovery time 4, so 5's subtree has another way up to 4 or an ancestor. 4's own low-link drops to 3. Edge (4, 5) is not a bridge.
  12. Back from 4: its low-link 3 reaches at or before 3's discovery time 3, so 4's subtree has another way up to 3 or an ancestor. 3's own low-link drops to 3. Edge (3, 4) is not a bridge.
  13. Back from 3: its low-link is 3, which is HIGHER than 2's own discovery time 2 — nothing in 3's subtree can reach 2 or anything above it any other way. Edge (2, 3) is a bridge.
  14. Back from 2: its low-link 0 reaches at or before 1's discovery time 1, so 2's subtree has another way up to 1 or an ancestor. 1's own low-link drops to 0. Edge (1, 2) is not a bridge.
  15. Back from 1: its low-link 0 reaches at or before 0's discovery time 0, so 1's subtree has another way up to 0 or an ancestor. 0's own low-link drops to 0. Edge (0, 1) is not a bridge.
  16. DFS complete. 2 bridges found: (5, 6), (2, 3). Every other edge belongs to a triangle, so a cycle already backs it up if it were removed.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Critical Connections in a Network in the editorAll Graph problemsBack to roadmap