38.02Intermediate / Advanced4 topics15 min4 interactive animations

Bridges

A bridge is an edge whose loss splits the graph; one DFS with low-link finds all of them, and the same pass yields the 2-edge-connected components and the bridge tree.

Learning goals

State and apply the test low[v] > tin[u] for a tree edge u-v
Group vertices into 2-edge-connected components with a stack
Build the bridge tree and explain why it is a tree
Solve the Critical Connections problem

Prerequisites

DFS timestamps and low-link

A road network has weak links: a single bridge that, if closed, cuts a town off. Finding every such link without trying each closure one by one is what low-link does.

38.02.1

Tarjan low-link bridge detection

An edge is a **bridge** when removing it increases the number of connected components. Only tree edges can be bridges: a back edge lies on a cycle with part of the tree path, so removing it never disconnects anything.

For a tree edge u-v (u the parent) the rule is **low[v] > tin[u]**. It says: nothing in v's subtree has a back edge to u or above, so the only way across is this edge. If instead low[v] <= tin[u] some back edge climbs back to u (or higher), giving a second route.

On the “Two cycles joined by one bridge” preset (0-1 1-2 2-0 3-4 4-5 5-3 2-3, start 0), vertex 3 gets tin = 4 and low = 4. When the DFS returns from 3 to 2, low[3] = 4 > tin[2] = 3, so 2-3 is a bridge. The cycle edges fail the test: for example low[1] = 1 <= tin[0] = 1.

Run the whole algorithm once from every unvisited vertex; the total work is O(n + m). The result is a list of edge ids, which stays correct for graphs with parallel edges.

Java

1static class BridgeDfs {
2    int timer = 0, comps = 0;
3    int[] tin, low, comp;                               // comp[v]: 2-edge-connected component of v
4    Deque<Integer> stack = new ArrayDeque<>();
5    List<Integer> bridges = new ArrayList<>();          // edge ids
6    List<int[]>[] g;                                    // g[u] holds {neighbour, edge id}
7
8    @SuppressWarnings("unchecked")
9    BridgeDfs(int n, int[][] edges) {
10        tin = new int[n]; low = new int[n]; comp = new int[n];
11        g = new List[n];
12        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
13        for (int k = 0; k < edges.length; k++) {
14            g[edges[k][0]].add(new int[]{edges[k][1], k});
15            g[edges[k][1]].add(new int[]{edges[k][0], k});
16        }
17    }
18
19    void runAll() {
20        for (int v = 0; v < tin.length; v++) if (tin[v] == 0) dfs(v, -1);
21    }
22
23    void dfs(int u, int parentEdge) {
24        tin[u] = low[u] = ++timer;
25        stack.push(u);
26        for (int[] e : g[u]) {
27            int v = e[0], id = e[1];
28            if (id == parentEdge) continue;
29            if (tin[v] != 0) {
30                low[u] = Math.min(low[u], tin[v]);
31            } else {
32                dfs(v, id);
33                low[u] = Math.min(low[u], low[v]);
34                if (low[v] > tin[u]) bridges.add(id);   // nothing below v reaches u or above
35            }
36        }
37        if (low[u] == tin[u]) {                         // u heads a 2-edge-connected component
38            int x;
39            do { x = stack.pop(); comp[x] = comps; } while (x != u);
40            comps++;
41        }
42    }
43}
44
45static List<Integer> findBridges(int n, int[][] edges) {
46    BridgeDfs b = new BridgeDfs(n, edges);
47    b.runAll();
48    return b.bridges;
49}

Worst

O(n + m)

Space

O(n + m)

Bridges by low-link, 2-edge-connected components, bridge tree

Interactive · edit the input

node caption: tin / low; colour = 2-edge-connected component · 6 vertices · 7 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexBridge

tin

–0

–1

–2

–3

–4

–5

low

–0

–1

–2

–3

–4

–5

vertex stack (top on the right)

empty

2-edge-connected components

none yet

Setup

A bridge is an edge whose removal splits its component. Run the DFS with low-link: a tree edge u-v is a bridge exactly when low[v] > tin[u], that is, nothing in v's subtree can climb back to u or above. DFS starts at 0.

Step 1 / 34

Java

1static int timer = 0, comps = 0;
2static int[] tin, low, comp;                          // comp[v]: 2-edge-connected component of v
3static Deque<Integer> stack = new ArrayDeque<>();
4static List<int[]> bridges = new ArrayList<>();       // {u, v} for each bridge
5static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
6    tin[u] = low[u] = ++timer;
7    stack.push(u);
8    for (int[] e : g[u]) {
9        int v = e[0], id = e[1];
10        if (id == parentEdge) continue;               // skip the edge we came by, not every edge to the parent
11        if (tin[v] != 0) {
12            low[u] = Math.min(low[u], tin[v]);        // back edge
13        } else {
14            dfs(g, v, id);
15            low[u] = Math.min(low[u], low[v]);
16            if (low[v] > tin[u]) bridges.add(new int[]{u, v});   // nothing below v reaches u or above: bridge
17        }
18    }
19    if (low[u] == tin[u]) {                           // u heads a 2-edge-connected component
20        int x;
21        do { x = stack.pop(); comp[x] = comps; } while (x != u);
22        comps++;
23    }
24}

Live state

0 bridges0 components

edges

No condition evaluated on this step

Execution trace (dry run table)Show 34 steps

Step	Line	State	What happens
1	L1	n=6 edges=7	A bridge is an edge whose removal splits its component. Run the DFS with low-link: a tree edge u-v is a bridge exactly when low[v] > tin[u], that is, nothing in v's subtree can climb back to u or above. DFS starts at 0.
2	L1	root=0	0 has not been visited: start a new DFS tree here.
3	L7	u=0 tin=1	Enter 0 (tin = low = 1) and push it on the vertex stack.
4	L14	u=0 v=1	Tree edge 0-1: go down into 1.
5	L7	u=1 tin=2	Enter 1 (tin = low = 2) and push it on the vertex stack.
6	L10	u=1 edge=0-1	Skip 0-1: it is the edge used to reach 1. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
7	L14	u=1 v=2	Tree edge 1-2: go down into 2.
8	L7	u=2 tin=3	Enter 2 (tin = low = 3) and push it on the vertex stack.
9	L10	u=2 edge=1-2	Skip 1-2: it is the edge used to reach 2. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
10	L12	u=2 v=0 low=1	2-0 is a back edge to ancestor 0 (tin 1): low[2] drops from 3 to 1.
11	L14	u=2 v=3	Tree edge 2-3: go down into 3.
12	L7	u=3 tin=4	Enter 3 (tin = low = 4) and push it on the vertex stack.
13	L14	u=3 v=4	Tree edge 3-4: go down into 4.
14	L7	u=4 tin=5	Enter 4 (tin = low = 5) and push it on the vertex stack.
15	L10	u=4 edge=3-4	Skip 3-4: it is the edge used to reach 4. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
16	L14	u=4 v=5	Tree edge 4-5: go down into 5.
17	L7	u=5 tin=6	Enter 5 (tin = low = 6) and push it on the vertex stack.
18	L10	u=5 edge=4-5	Skip 4-5: it is the edge used to reach 5. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
19	L12	u=5 v=3 low=4	5-3 is a back edge to ancestor 3 (tin 4): low[5] drops from 6 to 4.
20	L19	u=5	low[5] = 4 < tin[5] = 6: 5 stays on the stack with its parent's component.
21	L16	u=4 v=5 low_v=4 tin_u=5	low[5] = 4 ≤ tin[4] = 5: some back edge from 5's subtree reaches 4 or above, so 4-5 is not a bridge. low[4] drops from 5 to 4.
22	L19	u=4	low[4] = 4 < tin[4] = 5: 4 stays on the stack with its parent's component.
23	L16	u=3 v=4 low_v=4 tin_u=4	low[4] = 4 ≤ tin[3] = 4: some back edge from 4's subtree reaches 3 or above, so 3-4 is not a bridge. low[3] stays 4.
24	L11	u=3 v=5	5 is a younger, already finished vertex: 5-3 is the back edge seen from above and changes nothing.
25	L10	u=3 edge=2-3	Skip 2-3: it is the edge used to reach 3. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
26	L19	u=3 component={3,4,5}	low[3] = tin[3]: 3 heads a 2-edge-connected component. Pop the stack down to 3: {3,4,5}.
27	L16	u=2 v=3 low_v=4 tin_u=3	low[3] = 4 > tin[2] = 3: the subtree of 3 cannot get back to 2 or above, so 2-3 is a bridge.
28	L19	u=2	low[2] = 1 < tin[2] = 3: 2 stays on the stack with its parent's component.
29	L16	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 ≤ tin[1] = 2: some back edge from 2's subtree reaches 1 or above, so 1-2 is not a bridge. low[1] drops from 2 to 1.
30	L19	u=1	low[1] = 1 < tin[1] = 2: 1 stays on the stack with its parent's component.
31	L16	u=0 v=1 low_v=1 tin_u=1	low[1] = 1 ≤ tin[0] = 1: some back edge from 1's subtree reaches 0 or above, so 0-1 is not a bridge. low[0] stays 1.
32	L11	u=0 v=2	2 is a younger, already finished vertex: 2-0 is the back edge seen from above and changes nothing.
33	L19	u=0 component={0,1,2}	low[0] = tin[0]: 0 heads a 2-edge-connected component. Pop the stack down to 0: {0,1,2}.
34	L19	return=1 bridges=1 components=2	1 bridge and 2 2-edge-connected components. Contracting each component to one point leaves the bridge tree: its edges are exactly the one bridge, and it has no cycles.

38.02.2

2-edge-connected components

Delete all bridges and the graph falls apart into **2-edge-connected components**: groups of vertices where any two are joined by two edge-disjoint paths, so no single edge removal separates them.

The same DFS finds them with a vertex stack. Push each vertex on entry. When low[u] == tin[u], no back edge lets u's subtree climb above u, so u is the top of a component: pop the stack down to u, and everything popped is one component. (low[u] == tin[u] is the same test as “the edge to the parent is a bridge”, or u is a root.)

On the “Two cycles joined by one bridge” preset the stack empties twice: first after vertex 3 finishes, popping {3, 4, 5}, then when the root 0 finishes, popping {0, 1, 2}. The animation colours each component as it is popped. On the “A tree: every edge is a bridge” preset no cycles exist, so each of the 5 vertices is its own component.

Java

1static int[] twoEdgeComponents(int n, int[][] edges) {   // comp[v]: component number of vertex v
2    BridgeDfs b = new BridgeDfs(n, edges);
3    b.runAll();
4    return b.comp;
5}

Bridges by low-link, 2-edge-connected components, bridge tree

Interactive · edit the input

node caption: tin / low; colour = 2-edge-connected component · 6 vertices · 7 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexBridge

tin

–0

–1

–2

–3

–4

–5

low

–0

–1

–2

–3

–4

–5

vertex stack (top on the right)

empty

2-edge-connected components

none yet

Setup

Step 1 / 34

Java

1static int timer = 0, comps = 0;
2static int[] tin, low, comp;                          // comp[v]: 2-edge-connected component of v
3static Deque<Integer> stack = new ArrayDeque<>();
4static List<int[]> bridges = new ArrayList<>();       // {u, v} for each bridge
5static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
6    tin[u] = low[u] = ++timer;
7    stack.push(u);
8    for (int[] e : g[u]) {
9        int v = e[0], id = e[1];
10        if (id == parentEdge) continue;               // skip the edge we came by, not every edge to the parent
11        if (tin[v] != 0) {
12            low[u] = Math.min(low[u], tin[v]);        // back edge
13        } else {
14            dfs(g, v, id);
15            low[u] = Math.min(low[u], low[v]);
16            if (low[v] > tin[u]) bridges.add(new int[]{u, v});   // nothing below v reaches u or above: bridge
17        }
18    }
19    if (low[u] == tin[u]) {                           // u heads a 2-edge-connected component
20        int x;
21        do { x = stack.pop(); comp[x] = comps; } while (x != u);
22        comps++;
23    }
24}

Live state

0 bridges0 components

edges

No condition evaluated on this step

Execution trace (dry run table)Show 34 steps

Step	Line	State	What happens
1	L1	n=6 edges=7	A bridge is an edge whose removal splits its component. Run the DFS with low-link: a tree edge u-v is a bridge exactly when low[v] > tin[u], that is, nothing in v's subtree can climb back to u or above. DFS starts at 0.
2	L1	root=0	0 has not been visited: start a new DFS tree here.
3	L7	u=0 tin=1	Enter 0 (tin = low = 1) and push it on the vertex stack.
4	L14	u=0 v=1	Tree edge 0-1: go down into 1.
5	L7	u=1 tin=2	Enter 1 (tin = low = 2) and push it on the vertex stack.
6	L10	u=1 edge=0-1	Skip 0-1: it is the edge used to reach 1. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
7	L14	u=1 v=2	Tree edge 1-2: go down into 2.
8	L7	u=2 tin=3	Enter 2 (tin = low = 3) and push it on the vertex stack.
9	L10	u=2 edge=1-2	Skip 1-2: it is the edge used to reach 2. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
10	L12	u=2 v=0 low=1	2-0 is a back edge to ancestor 0 (tin 1): low[2] drops from 3 to 1.
11	L14	u=2 v=3	Tree edge 2-3: go down into 3.
12	L7	u=3 tin=4	Enter 3 (tin = low = 4) and push it on the vertex stack.
13	L14	u=3 v=4	Tree edge 3-4: go down into 4.
14	L7	u=4 tin=5	Enter 4 (tin = low = 5) and push it on the vertex stack.
15	L10	u=4 edge=3-4	Skip 3-4: it is the edge used to reach 4. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
16	L14	u=4 v=5	Tree edge 4-5: go down into 5.
17	L7	u=5 tin=6	Enter 5 (tin = low = 6) and push it on the vertex stack.
18	L10	u=5 edge=4-5	Skip 4-5: it is the edge used to reach 5. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
19	L12	u=5 v=3 low=4	5-3 is a back edge to ancestor 3 (tin 4): low[5] drops from 6 to 4.
20	L19	u=5	low[5] = 4 < tin[5] = 6: 5 stays on the stack with its parent's component.
21	L16	u=4 v=5 low_v=4 tin_u=5	low[5] = 4 ≤ tin[4] = 5: some back edge from 5's subtree reaches 4 or above, so 4-5 is not a bridge. low[4] drops from 5 to 4.
22	L19	u=4	low[4] = 4 < tin[4] = 5: 4 stays on the stack with its parent's component.
23	L16	u=3 v=4 low_v=4 tin_u=4	low[4] = 4 ≤ tin[3] = 4: some back edge from 4's subtree reaches 3 or above, so 3-4 is not a bridge. low[3] stays 4.
24	L11	u=3 v=5	5 is a younger, already finished vertex: 5-3 is the back edge seen from above and changes nothing.
25	L10	u=3 edge=2-3	Skip 2-3: it is the edge used to reach 3. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
26	L19	u=3 component={3,4,5}	low[3] = tin[3]: 3 heads a 2-edge-connected component. Pop the stack down to 3: {3,4,5}.
27	L16	u=2 v=3 low_v=4 tin_u=3	low[3] = 4 > tin[2] = 3: the subtree of 3 cannot get back to 2 or above, so 2-3 is a bridge.
28	L19	u=2	low[2] = 1 < tin[2] = 3: 2 stays on the stack with its parent's component.
29	L16	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 ≤ tin[1] = 2: some back edge from 2's subtree reaches 1 or above, so 1-2 is not a bridge. low[1] drops from 2 to 1.
30	L19	u=1	low[1] = 1 < tin[1] = 2: 1 stays on the stack with its parent's component.
31	L16	u=0 v=1 low_v=1 tin_u=1	low[1] = 1 ≤ tin[0] = 1: some back edge from 1's subtree reaches 0 or above, so 0-1 is not a bridge. low[0] stays 1.
32	L11	u=0 v=2	2 is a younger, already finished vertex: 2-0 is the back edge seen from above and changes nothing.
33	L19	u=0 component={0,1,2}	low[0] = tin[0]: 0 heads a 2-edge-connected component. Pop the stack down to 0: {0,1,2}.
34	L19	return=1 bridges=1 components=2	1 bridge and 2 2-edge-connected components. Contracting each component to one point leaves the bridge tree: its edges are exactly the one bridge, and it has no cycles.

38.02.3

Bridge tree

Shrink every 2-edge-connected component to a single point and keep the bridges as edges between them. The result is the **bridge tree** (a forest if the graph is disconnected). It has no cycles: a cycle of bridges would make each of its edges non-bridges.

The bridge tree turns questions about the graph into questions about a tree. How many edges must be added to make the graph 2-edge-connected? Look at the leaves of the bridge tree (the last lesson of this chapter, Graph Robustness). Which bridges lie on the path between two vertices? Walk the tree path between their components.

For a connected graph with c components after contracting, the tree has c - 1 edges. The “Two cycles joined by one bridge” preset gives 2 components and 1 bridge; the “A parallel edge removes the bridge” preset (0-1 0-1 1-2) gives components {0, 1} and {2} joined by the single bridge 1-2.

Java

1static List<int[]> bridgeTree(int n, int[][] edges) {   // each pair {a, b} joins two component numbers
2    BridgeDfs b = new BridgeDfs(n, edges);
3    b.runAll();
4    List<int[]> tree = new ArrayList<>();
5    for (int id : b.bridges) tree.add(new int[]{b.comp[edges[id][0]], b.comp[edges[id][1]]});
6    return tree;
7}

Bridges by low-link, 2-edge-connected components, bridge tree

Interactive · edit the input

node caption: tin / low; colour = 2-edge-connected component · 6 vertices · 7 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexBridge

tin

–0

–1

–2

–3

–4

–5

low

–0

–1

–2

–3

–4

–5

vertex stack (top on the right)

empty

2-edge-connected components

none yet

Setup

Step 1 / 34

Java

1static int timer = 0, comps = 0;
2static int[] tin, low, comp;                          // comp[v]: 2-edge-connected component of v
3static Deque<Integer> stack = new ArrayDeque<>();
4static List<int[]> bridges = new ArrayList<>();       // {u, v} for each bridge
5static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
6    tin[u] = low[u] = ++timer;
7    stack.push(u);
8    for (int[] e : g[u]) {
9        int v = e[0], id = e[1];
10        if (id == parentEdge) continue;               // skip the edge we came by, not every edge to the parent
11        if (tin[v] != 0) {
12            low[u] = Math.min(low[u], tin[v]);        // back edge
13        } else {
14            dfs(g, v, id);
15            low[u] = Math.min(low[u], low[v]);
16            if (low[v] > tin[u]) bridges.add(new int[]{u, v});   // nothing below v reaches u or above: bridge
17        }
18    }
19    if (low[u] == tin[u]) {                           // u heads a 2-edge-connected component
20        int x;
21        do { x = stack.pop(); comp[x] = comps; } while (x != u);
22        comps++;
23    }
24}

Live state

0 bridges0 components

edges

No condition evaluated on this step

Execution trace (dry run table)Show 34 steps

Step	Line	State	What happens
1	L1	n=6 edges=7	A bridge is an edge whose removal splits its component. Run the DFS with low-link: a tree edge u-v is a bridge exactly when low[v] > tin[u], that is, nothing in v's subtree can climb back to u or above. DFS starts at 0.
2	L1	root=0	0 has not been visited: start a new DFS tree here.
3	L7	u=0 tin=1	Enter 0 (tin = low = 1) and push it on the vertex stack.
4	L14	u=0 v=1	Tree edge 0-1: go down into 1.
5	L7	u=1 tin=2	Enter 1 (tin = low = 2) and push it on the vertex stack.
6	L10	u=1 edge=0-1	Skip 0-1: it is the edge used to reach 1. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
7	L14	u=1 v=2	Tree edge 1-2: go down into 2.
8	L7	u=2 tin=3	Enter 2 (tin = low = 3) and push it on the vertex stack.
9	L10	u=2 edge=1-2	Skip 1-2: it is the edge used to reach 2. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
10	L12	u=2 v=0 low=1	2-0 is a back edge to ancestor 0 (tin 1): low[2] drops from 3 to 1.
11	L14	u=2 v=3	Tree edge 2-3: go down into 3.
12	L7	u=3 tin=4	Enter 3 (tin = low = 4) and push it on the vertex stack.
13	L14	u=3 v=4	Tree edge 3-4: go down into 4.
14	L7	u=4 tin=5	Enter 4 (tin = low = 5) and push it on the vertex stack.
15	L10	u=4 edge=3-4	Skip 3-4: it is the edge used to reach 4. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
16	L14	u=4 v=5	Tree edge 4-5: go down into 5.
17	L7	u=5 tin=6	Enter 5 (tin = low = 6) and push it on the vertex stack.
18	L10	u=5 edge=4-5	Skip 4-5: it is the edge used to reach 5. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
19	L12	u=5 v=3 low=4	5-3 is a back edge to ancestor 3 (tin 4): low[5] drops from 6 to 4.
20	L19	u=5	low[5] = 4 < tin[5] = 6: 5 stays on the stack with its parent's component.
21	L16	u=4 v=5 low_v=4 tin_u=5	low[5] = 4 ≤ tin[4] = 5: some back edge from 5's subtree reaches 4 or above, so 4-5 is not a bridge. low[4] drops from 5 to 4.
22	L19	u=4	low[4] = 4 < tin[4] = 5: 4 stays on the stack with its parent's component.
23	L16	u=3 v=4 low_v=4 tin_u=4	low[4] = 4 ≤ tin[3] = 4: some back edge from 4's subtree reaches 3 or above, so 3-4 is not a bridge. low[3] stays 4.
24	L11	u=3 v=5	5 is a younger, already finished vertex: 5-3 is the back edge seen from above and changes nothing.
25	L10	u=3 edge=2-3	Skip 2-3: it is the edge used to reach 3. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
26	L19	u=3 component={3,4,5}	low[3] = tin[3]: 3 heads a 2-edge-connected component. Pop the stack down to 3: {3,4,5}.
27	L16	u=2 v=3 low_v=4 tin_u=3	low[3] = 4 > tin[2] = 3: the subtree of 3 cannot get back to 2 or above, so 2-3 is a bridge.
28	L19	u=2	low[2] = 1 < tin[2] = 3: 2 stays on the stack with its parent's component.
29	L16	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 ≤ tin[1] = 2: some back edge from 2's subtree reaches 1 or above, so 1-2 is not a bridge. low[1] drops from 2 to 1.
30	L19	u=1	low[1] = 1 < tin[1] = 2: 1 stays on the stack with its parent's component.
31	L16	u=0 v=1 low_v=1 tin_u=1	low[1] = 1 ≤ tin[0] = 1: some back edge from 1's subtree reaches 0 or above, so 0-1 is not a bridge. low[0] stays 1.
32	L11	u=0 v=2	2 is a younger, already finished vertex: 2-0 is the back edge seen from above and changes nothing.
33	L19	u=0 component={0,1,2}	low[0] = tin[0]: 0 heads a 2-edge-connected component. Pop the stack down to 0: {0,1,2}.
34	L19	return=1 bridges=1 components=2	1 bridge and 2 2-edge-connected components. Contracting each component to one point leaves the bridge tree: its edges are exactly the one bridge, and it has no cycles.

38.02.4

Critical connections

**Critical Connections in a Network** (LeetCode 1192) asks for every connection whose removal splits the network: exactly the bridges. The input is a simple graph (no repeated connections), so skipping the parent by vertex is safe here, and the standard solution is a few lines.

The code below is the interview-style answer. For a general input that may contain parallel edges use the edge-id version from the first item instead.

Recursion depth can reach n; LeetCode allows n up to 100 000 and Java may overflow the default stack on a long path. In an interview mention it and say you would use an explicit stack or a larger thread stack.

Java

1static class Critical {
2    int timer = 0;
3    int[] tin, low;
4    List<Integer>[] g;
5    List<List<Integer>> out = new ArrayList<>();
6
7    @SuppressWarnings("unchecked")
8    Critical(int n, List<List<Integer>> connections) {
9        tin = new int[n]; low = new int[n];
10        g = new List[n];
11        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
12        for (List<Integer> c : connections) { g[c.get(0)].add(c.get(1)); g[c.get(1)].add(c.get(0)); }
13    }
14
15    void dfs(int u, int parent) {
16        tin[u] = low[u] = ++timer;
17        for (int v : g[u]) {
18            if (v == parent) continue;                  // safe only because the graph has no parallel edges
19            if (tin[v] != 0) {
20                low[u] = Math.min(low[u], tin[v]);
21            } else {
22                dfs(v, u);
23                low[u] = Math.min(low[u], low[v]);
24                if (low[v] > tin[u]) out.add(List.of(u, v));
25            }
26        }
27    }
28}
29
30static List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
31    Critical c = new Critical(n, connections);
32    for (int v = 0; v < n; v++) if (c.tin[v] == 0) c.dfs(v, -1);
33    return c.out;
34}

Bridges by low-link, 2-edge-connected components, bridge tree

Interactive · edit the input

node caption: tin / low; colour = 2-edge-connected component · 6 vertices · 7 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexBridge

tin

–0

–1

–2

–3

–4

–5

low

–0

–1

–2

–3

–4

–5

vertex stack (top on the right)

empty

2-edge-connected components

none yet

Setup

Step 1 / 34

Java

1static int timer = 0, comps = 0;
2static int[] tin, low, comp;                          // comp[v]: 2-edge-connected component of v
3static Deque<Integer> stack = new ArrayDeque<>();
4static List<int[]> bridges = new ArrayList<>();       // {u, v} for each bridge
5static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
6    tin[u] = low[u] = ++timer;
7    stack.push(u);
8    for (int[] e : g[u]) {
9        int v = e[0], id = e[1];
10        if (id == parentEdge) continue;               // skip the edge we came by, not every edge to the parent
11        if (tin[v] != 0) {
12            low[u] = Math.min(low[u], tin[v]);        // back edge
13        } else {
14            dfs(g, v, id);
15            low[u] = Math.min(low[u], low[v]);
16            if (low[v] > tin[u]) bridges.add(new int[]{u, v});   // nothing below v reaches u or above: bridge
17        }
18    }
19    if (low[u] == tin[u]) {                           // u heads a 2-edge-connected component
20        int x;
21        do { x = stack.pop(); comp[x] = comps; } while (x != u);
22        comps++;
23    }
24}

Live state

0 bridges0 components

edges

No condition evaluated on this step

Execution trace (dry run table)Show 34 steps

Step	Line	State	What happens
1	L1	n=6 edges=7	A bridge is an edge whose removal splits its component. Run the DFS with low-link: a tree edge u-v is a bridge exactly when low[v] > tin[u], that is, nothing in v's subtree can climb back to u or above. DFS starts at 0.
2	L1	root=0	0 has not been visited: start a new DFS tree here.
3	L7	u=0 tin=1	Enter 0 (tin = low = 1) and push it on the vertex stack.
4	L14	u=0 v=1	Tree edge 0-1: go down into 1.
5	L7	u=1 tin=2	Enter 1 (tin = low = 2) and push it on the vertex stack.
6	L10	u=1 edge=0-1	Skip 0-1: it is the edge used to reach 1. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
7	L14	u=1 v=2	Tree edge 1-2: go down into 2.
8	L7	u=2 tin=3	Enter 2 (tin = low = 3) and push it on the vertex stack.
9	L10	u=2 edge=1-2	Skip 1-2: it is the edge used to reach 2. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
10	L12	u=2 v=0 low=1	2-0 is a back edge to ancestor 0 (tin 1): low[2] drops from 3 to 1.
11	L14	u=2 v=3	Tree edge 2-3: go down into 3.
12	L7	u=3 tin=4	Enter 3 (tin = low = 4) and push it on the vertex stack.
13	L14	u=3 v=4	Tree edge 3-4: go down into 4.
14	L7	u=4 tin=5	Enter 4 (tin = low = 5) and push it on the vertex stack.
15	L10	u=4 edge=3-4	Skip 3-4: it is the edge used to reach 4. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
16	L14	u=4 v=5	Tree edge 4-5: go down into 5.
17	L7	u=5 tin=6	Enter 5 (tin = low = 6) and push it on the vertex stack.
18	L10	u=5 edge=4-5	Skip 4-5: it is the edge used to reach 5. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
19	L12	u=5 v=3 low=4	5-3 is a back edge to ancestor 3 (tin 4): low[5] drops from 6 to 4.
20	L19	u=5	low[5] = 4 < tin[5] = 6: 5 stays on the stack with its parent's component.
21	L16	u=4 v=5 low_v=4 tin_u=5	low[5] = 4 ≤ tin[4] = 5: some back edge from 5's subtree reaches 4 or above, so 4-5 is not a bridge. low[4] drops from 5 to 4.
22	L19	u=4	low[4] = 4 < tin[4] = 5: 4 stays on the stack with its parent's component.
23	L16	u=3 v=4 low_v=4 tin_u=4	low[4] = 4 ≤ tin[3] = 4: some back edge from 4's subtree reaches 3 or above, so 3-4 is not a bridge. low[3] stays 4.
24	L11	u=3 v=5	5 is a younger, already finished vertex: 5-3 is the back edge seen from above and changes nothing.
25	L10	u=3 edge=2-3	Skip 2-3: it is the edge used to reach 3. A parallel copy of it would be a back edge and would keep the edge from being a bridge.
26	L19	u=3 component={3,4,5}	low[3] = tin[3]: 3 heads a 2-edge-connected component. Pop the stack down to 3: {3,4,5}.
27	L16	u=2 v=3 low_v=4 tin_u=3	low[3] = 4 > tin[2] = 3: the subtree of 3 cannot get back to 2 or above, so 2-3 is a bridge.
28	L19	u=2	low[2] = 1 < tin[2] = 3: 2 stays on the stack with its parent's component.
29	L16	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 ≤ tin[1] = 2: some back edge from 2's subtree reaches 1 or above, so 1-2 is not a bridge. low[1] drops from 2 to 1.
30	L19	u=1	low[1] = 1 < tin[1] = 2: 1 stays on the stack with its parent's component.
31	L16	u=0 v=1 low_v=1 tin_u=1	low[1] = 1 ≤ tin[0] = 1: some back edge from 1's subtree reaches 0 or above, so 0-1 is not a bridge. low[0] stays 1.
32	L11	u=0 v=2	2 is a younger, already finished vertex: 2-0 is the back edge seen from above and changes nothing.
33	L19	u=0 component={0,1,2}	low[0] = tin[0]: 0 heads a 2-edge-connected component. Pop the stack down to 0: {0,1,2}.
34	L19	return=1 bridges=1 components=2	1 bridge and 2 2-edge-connected components. Contracting each component to one point leaves the bridge tree: its edges are exactly the one bridge, and it has no cycles.

Practice ladder

Now try it yourself

Easy

Find Center of Star Graph

Medium

Critical Connections in a Network
Number of Provinces

Advanced

Minimum Number of Days to Disconnect Island
Remove Max Number of Edges to Keep Graph Fully Traversable

Key takeaways

A tree edge u-v is a bridge exactly when low[v] > tin[u].
The vertex stack pops one 2-edge-connected component whenever low[u] == tin[u].
Contracting components leaves the bridge tree: a forest whose edges are the bridges.