38.03Intermediate / Advanced4 topics16 min4 interactive animations

Articulation points

An articulation point is a vertex whose removal splits its component. The low-link test needs a small change (>= instead of >) and a special rule for the DFS root, and an edge stack collects the biconnected blocks.

Learning goals

Apply the non-root test low[v] >= tin[u] and the root rule of two children
Explain why the root needs its own rule
Collect biconnected blocks with an edge stack
Build the block-cut tree from blocks and cut vertices

Prerequisites

Bridges and low-link

In a network of routers, a few routers are single points of failure: if one dies, part of the network is cut off. Those are the articulation points, and the pieces between them are the blocks.

38.03.1

Root exception

A vertex u is an **articulation point** (cut vertex) if removing it, with its edges, increases the number of connected components.

For a non-root u with DFS child v, u separates v's subtree when low[v] >= tin[u]: nothing in the subtree can climb strictly above u. The root u has no vertex above it, so every child satisfies low[v] >= tin[u] automatically, and the test would call the root a cut vertex every time. Instead the root is a cut vertex exactly when it has **two or more DFS children**: with one child, removing the root leaves that child's subtree connected; with two or more, no edge joins their subtrees (there are no cross edges in an undirected DFS).

The “Bowtie: two triangles share vertex 2” preset shows both rules. Start at 0: vertex 2 is a non-root, its child 3 has low = 3 >= tin[2] = 3, so 2 is a cut vertex. Now load “Root exception: start at the cut vertex”: the DFS root is 2 itself, every low is 1, and 2 is a cut vertex only because it has 2 DFS children. Start at a non-cut vertex like 0 in the same graph and the root has a single child, so it is correctly not reported.

The set of cut vertices does not depend on where the DFS starts, even though the roles and the numbers do.

Java

1static class CutVertices {
2    int timer = 0;
3    int[] tin, low;
4    boolean[] cut;
5    List<int[]>[] g;                                    // g[u] holds {neighbour, edge id}
6
7    @SuppressWarnings("unchecked")
8    CutVertices(int n, int[][] edges) {
9        tin = new int[n]; low = new int[n]; cut = new boolean[n];
10        g = new List[n];
11        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
12        for (int k = 0; k < edges.length; k++) {
13            g[edges[k][0]].add(new int[]{edges[k][1], k});
14            g[edges[k][1]].add(new int[]{edges[k][0], k});
15        }
16    }
17
18    void dfs(int u, int parentEdge) {
19        tin[u] = low[u] = ++timer;
20        int children = 0;
21        for (int[] e : g[u]) {
22            int v = e[0], id = e[1];
23            if (id == parentEdge) continue;
24            if (tin[v] != 0) {
25                low[u] = Math.min(low[u], tin[v]);
26            } else {
27                children++;
28                dfs(v, id);
29                low[u] = Math.min(low[u], low[v]);
30                if (parentEdge != -1 && low[v] >= tin[u]) cut[u] = true;   // non-root: v's subtree cannot get above u
31            }
32        }
33        if (parentEdge == -1 && children >= 2) cut[u] = true;           // root: two or more children
34    }
35}
36
37static boolean[] articulationPoints(int n, int[][] edges) {
38    CutVertices c = new CutVertices(n, edges);
39    for (int v = 0; v < n; v++) if (c.tin[v] == 0) c.dfs(v, -1);
40    return c.cut;
41}

Worst

O(n + m)

Space

O(n + m)

Articulation points, the root exception, biconnected blocks

Interactive · edit the input

node caption: tin / low; edge colour = block · 5 vertices · 6 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexArticulation point

tin

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

edge stack (top on the right)

empty

blocks (vertex sets)

none yet

Setup

An articulation point (cut vertex) is a vertex whose removal splits its component. For a non-root u with DFS child v the test is low[v] ≥ tin[u] (v's subtree cannot climb above u). The DFS root is special: it is a cut vertex only if it has two or more children. DFS root: 0.

Step 1 / 29

Java

1static int timer = 0;
2static int[] tin, low;
3static boolean[] cut;                                 // cut[v]: v is an articulation point
4static Deque<Integer> edgeStack = new ArrayDeque<>();
5static List<List<Integer>> blocks = new ArrayList<>();   // each block as a list of edge ids
6static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
7    tin[u] = low[u] = ++timer;
8    int children = 0;
9    for (int[] e : g[u]) {
10        int v = e[0], id = e[1];
11        if (id == parentEdge) continue;
12        if (tin[v] == 0) {
13            children++;
14            edgeStack.push(id);                       // tree edge goes on the edge stack
15            dfs(g, v, id);
16            low[u] = Math.min(low[u], low[v]);
17            if (low[v] >= tin[u]) {                   // v's subtree cannot get above u: u separates it
18                if (parentEdge != -1) cut[u] = true;  // root is judged separately below
19                List<Integer> block = new ArrayList<>();
20                int x;
21                do { x = edgeStack.pop(); block.add(x); } while (x != id);
22                blocks.add(block);                    // pop one biconnected block
23            }
24        } else if (tin[v] < tin[u]) {                 // back edge to an ancestor: push it once, from its lower end
25            edgeStack.push(id);
26            low[u] = Math.min(low[u], tin[v]);
27        }
28    }
29    if (parentEdge == -1 && children >= 2) cut[u] = true;   // the root is a cut vertex only with two or more DFS children
30}

Live state

0 cut vertices0 blocks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L1	n=5 edges=6	An articulation point (cut vertex) is a vertex whose removal splits its component. For a non-root u with DFS child v the test is low[v] ≥ tin[u] (v's subtree cannot climb above u). The DFS root is special: it is a cut vertex only if it has two or more children. DFS root: 0.
2	L1	root=0	0 has not been visited: it becomes the root of a new DFS tree.
3	L7	u=0 tin=1	Enter 0: tin = low = 1.
4	L14	u=0 v=1 children=1	Tree edge 0-1: push it on the edge stack and go down into 1. 0 now has 1 DFS child.
5	L7	u=1 tin=2	Enter 1: tin = low = 2.
6	L11	u=1 edge=0-1	Skip 0-1: the edge used to reach 1.
7	L14	u=1 v=2 children=1	Tree edge 1-2: push it on the edge stack and go down into 2. 1 now has 1 DFS child.
8	L7	u=2 tin=3	Enter 2: tin = low = 3.
9	L11	u=2 edge=1-2	Skip 1-2: the edge used to reach 2.
10	L24	u=2 v=0 low=1	2-0 is a back edge up to 0: push it on the edge stack once, from its lower end. low[2] drops from 3 to 1.
11	L14	u=2 v=3 children=1	Tree edge 2-3: push it on the edge stack and go down into 3. 2 now has 1 DFS child.
12	L7	u=3 tin=4	Enter 3: tin = low = 4.
13	L11	u=3 edge=2-3	Skip 2-3: the edge used to reach 3.
14	L14	u=3 v=4 children=1	Tree edge 3-4: push it on the edge stack and go down into 4. 3 now has 1 DFS child.
15	L7	u=4 tin=5	Enter 4: tin = low = 5.
16	L11	u=4 edge=3-4	Skip 3-4: the edge used to reach 4.
17	L24	u=4 v=2 low=3	4-2 is a back edge up to 2: push it on the edge stack once, from its lower end. low[4] drops from 5 to 3.
18	L29	u=4	4 is finished.
19	L17	u=3 v=4 low_v=3 tin_u=4	low[4] = 3 < tin[3] = 4: 4's subtree has a back edge above 3, so 3 does not separate it. low[3] drops from 4 to 3.
20	L29	u=3	3 is finished.
21	L22	u=2 v=3 block={2,3,4}	low[3] = 3 ≥ tin[2] = 3: 3's subtree cannot get above 2. 2 is an articulation point. Pop the edge stack down to 2-3: block B1 = {2,3,4}.
22	L12	u=2 v=4	4 is a younger finished vertex: 4-2 was already pushed from 4's side.
23	L29	u=2	2 is finished.
24	L17	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 < tin[1] = 2: 2's subtree has a back edge above 1, so 1 does not separate it. low[1] drops from 2 to 1.
25	L29	u=1	1 is finished.
26	L22	u=0 v=1 block={0,1,2}	low[1] = 1 ≥ tin[0] = 1: 1's subtree cannot get above 0. 0 is the root: this alone proves nothing; it counts only if it gets a second child. Pop the edge stack down to 0-1: block B2 = {0,1,2}.
27	L12	u=0 v=2	2 is a younger finished vertex: 2-0 was already pushed from 2's side.
28	L29	u=0 children=1	0 is the root with 1 DFS child: fewer than two, so removing it leaves the rest connected: not an articulation point, even though every child satisfied low ≥ tin.
29	L29	return=1 cut_vertices={2} blocks=2	1 articulation point {2} and 2 blocks. The block-cut tree has a node per block and per cut vertex (3) and joins each cut vertex to the blocks containing it (2 links).

38.03.2

Low-link criterion

Bridges and cut vertices use the same two arrays and differ by one character. For a tree edge u-v: the edge is a bridge when low[v] > tin[u] (strictly above is impossible), and u separates v's subtree when low[v] >= tin[u] (reaching u itself is not enough, because u is the vertex being removed).

The difference matters. A cycle has no bridge and no cut vertex: the root has one child, and for every other vertex u its child's low value equals the root's entry time, which is below tin[u], so both tests fail. In the “Bowtie” preset the edge 2-3 is not a bridge (the triangle 2-3-4 gives low[3] = 3, not greater than tin[2] = 3), yet vertex 2 is a cut vertex (low[3] >= tin[2]): both statements are true, and both come from the same numbers.

Remember the root exception from the previous item: the >= test is applied to non-roots only.

Question	Tree edge u-v where u is the parent	Extra rule
Is u-v a bridge?	low[v] > tin[u]	none
Does u separate v's subtree?	low[v] >= tin[u]	root: needs 2 or more DFS children
Why different?	an edge cannot survive being removed	a vertex that is reached by a back edge is still removed

Articulation points, the root exception, biconnected blocks

Interactive · edit the input

node caption: tin / low; edge colour = block · 5 vertices · 6 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexArticulation point

tin

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

edge stack (top on the right)

empty

blocks (vertex sets)

none yet

Setup

Step 1 / 29

Java

1static int timer = 0;
2static int[] tin, low;
3static boolean[] cut;                                 // cut[v]: v is an articulation point
4static Deque<Integer> edgeStack = new ArrayDeque<>();
5static List<List<Integer>> blocks = new ArrayList<>();   // each block as a list of edge ids
6static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
7    tin[u] = low[u] = ++timer;
8    int children = 0;
9    for (int[] e : g[u]) {
10        int v = e[0], id = e[1];
11        if (id == parentEdge) continue;
12        if (tin[v] == 0) {
13            children++;
14            edgeStack.push(id);                       // tree edge goes on the edge stack
15            dfs(g, v, id);
16            low[u] = Math.min(low[u], low[v]);
17            if (low[v] >= tin[u]) {                   // v's subtree cannot get above u: u separates it
18                if (parentEdge != -1) cut[u] = true;  // root is judged separately below
19                List<Integer> block = new ArrayList<>();
20                int x;
21                do { x = edgeStack.pop(); block.add(x); } while (x != id);
22                blocks.add(block);                    // pop one biconnected block
23            }
24        } else if (tin[v] < tin[u]) {                 // back edge to an ancestor: push it once, from its lower end
25            edgeStack.push(id);
26            low[u] = Math.min(low[u], tin[v]);
27        }
28    }
29    if (parentEdge == -1 && children >= 2) cut[u] = true;   // the root is a cut vertex only with two or more DFS children
30}

Live state

0 cut vertices0 blocks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L1	n=5 edges=6	An articulation point (cut vertex) is a vertex whose removal splits its component. For a non-root u with DFS child v the test is low[v] ≥ tin[u] (v's subtree cannot climb above u). The DFS root is special: it is a cut vertex only if it has two or more children. DFS root: 0.
2	L1	root=0	0 has not been visited: it becomes the root of a new DFS tree.
3	L7	u=0 tin=1	Enter 0: tin = low = 1.
4	L14	u=0 v=1 children=1	Tree edge 0-1: push it on the edge stack and go down into 1. 0 now has 1 DFS child.
5	L7	u=1 tin=2	Enter 1: tin = low = 2.
6	L11	u=1 edge=0-1	Skip 0-1: the edge used to reach 1.
7	L14	u=1 v=2 children=1	Tree edge 1-2: push it on the edge stack and go down into 2. 1 now has 1 DFS child.
8	L7	u=2 tin=3	Enter 2: tin = low = 3.
9	L11	u=2 edge=1-2	Skip 1-2: the edge used to reach 2.
10	L24	u=2 v=0 low=1	2-0 is a back edge up to 0: push it on the edge stack once, from its lower end. low[2] drops from 3 to 1.
11	L14	u=2 v=3 children=1	Tree edge 2-3: push it on the edge stack and go down into 3. 2 now has 1 DFS child.
12	L7	u=3 tin=4	Enter 3: tin = low = 4.
13	L11	u=3 edge=2-3	Skip 2-3: the edge used to reach 3.
14	L14	u=3 v=4 children=1	Tree edge 3-4: push it on the edge stack and go down into 4. 3 now has 1 DFS child.
15	L7	u=4 tin=5	Enter 4: tin = low = 5.
16	L11	u=4 edge=3-4	Skip 3-4: the edge used to reach 4.
17	L24	u=4 v=2 low=3	4-2 is a back edge up to 2: push it on the edge stack once, from its lower end. low[4] drops from 5 to 3.
18	L29	u=4	4 is finished.
19	L17	u=3 v=4 low_v=3 tin_u=4	low[4] = 3 < tin[3] = 4: 4's subtree has a back edge above 3, so 3 does not separate it. low[3] drops from 4 to 3.
20	L29	u=3	3 is finished.
21	L22	u=2 v=3 block={2,3,4}	low[3] = 3 ≥ tin[2] = 3: 3's subtree cannot get above 2. 2 is an articulation point. Pop the edge stack down to 2-3: block B1 = {2,3,4}.
22	L12	u=2 v=4	4 is a younger finished vertex: 4-2 was already pushed from 4's side.
23	L29	u=2	2 is finished.
24	L17	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 < tin[1] = 2: 2's subtree has a back edge above 1, so 1 does not separate it. low[1] drops from 2 to 1.
25	L29	u=1	1 is finished.
26	L22	u=0 v=1 block={0,1,2}	low[1] = 1 ≥ tin[0] = 1: 1's subtree cannot get above 0. 0 is the root: this alone proves nothing; it counts only if it gets a second child. Pop the edge stack down to 0-1: block B2 = {0,1,2}.
27	L12	u=0 v=2	2 is a younger finished vertex: 2-0 was already pushed from 2's side.
28	L29	u=0 children=1	0 is the root with 1 DFS child: fewer than two, so removing it leaves the rest connected: not an articulation point, even though every child satisfied low ≥ tin.
29	L29	return=1 cut_vertices={2} blocks=2	1 articulation point {2} and 2 blocks. The block-cut tree has a node per block and per cut vertex (3) and joins each cut vertex to the blocks containing it (2 links).

38.03.3

Biconnected blocks

A **biconnected component** (or **block**) is a maximal piece of the graph with no cut vertex of its own: any two of its edges lie on a common simple cycle (or the block is a single edge). Blocks partition the **edges**; a cut vertex belongs to several blocks, an ordinary vertex to exactly one.

Collect them with an **edge stack**. Push every tree edge when DFS descends and every back edge once, from its lower end (tin[v] < tin[u]). After returning from a child v with low[v] >= tin[u], u separates v's subtree: pop edges down to and including the tree edge u-v. Those edges form one block.

On the “Bowtie” preset the edge stack is popped twice: block {2, 3, 4} when DFS finishes vertex 3 under 2, then block {0, 1, 2} at the end. The “A path: every inner vertex is a cut vertex” preset has 4 blocks (one per edge) and cut vertices 1, 2 and 3. A star with four leaves has 4 blocks meeting at its centre.

Java

1static class Blocks {
2    int timer = 0;
3    int[] tin, low;
4    Deque<Integer> edgeStack = new ArrayDeque<>();
5    List<List<Integer>> blocks = new ArrayList<>();     // each block is a list of edge ids
6    List<int[]>[] g;
7
8    @SuppressWarnings("unchecked")
9    Blocks(int n, int[][] edges) {
10        tin = new int[n]; low = 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 dfs(int u, int parentEdge) {
20        tin[u] = low[u] = ++timer;
21        for (int[] e : g[u]) {
22            int v = e[0], id = e[1];
23            if (id == parentEdge) continue;
24            if (tin[v] == 0) {
25                edgeStack.push(id);
26                dfs(v, id);
27                low[u] = Math.min(low[u], low[v]);
28                if (low[v] >= tin[u]) {                 // u separates v's subtree: pop one block
29                    List<Integer> block = new ArrayList<>();
30                    int x;
31                    do { x = edgeStack.pop(); block.add(x); } while (x != id);
32                    blocks.add(block);
33                }
34            } else if (tin[v] < tin[u]) {               // back edge up: push it once, from its lower end
35                edgeStack.push(id);
36                low[u] = Math.min(low[u], tin[v]);
37            }
38        }
39    }
40}
41
42static List<List<Integer>> biconnectedBlocks(int n, int[][] edges) {
43    Blocks b = new Blocks(n, edges);
44    for (int v = 0; v < n; v++) if (b.tin[v] == 0) b.dfs(v, -1);
45    return b.blocks;
46}

Worst

O(n + m)

Space

O(n + m)

Articulation points, the root exception, biconnected blocks

Interactive · edit the input

node caption: tin / low; edge colour = block · 5 vertices · 6 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexArticulation point

tin

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

edge stack (top on the right)

empty

blocks (vertex sets)

none yet

Setup

Step 1 / 29

Java

1static int timer = 0;
2static int[] tin, low;
3static boolean[] cut;                                 // cut[v]: v is an articulation point
4static Deque<Integer> edgeStack = new ArrayDeque<>();
5static List<List<Integer>> blocks = new ArrayList<>();   // each block as a list of edge ids
6static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
7    tin[u] = low[u] = ++timer;
8    int children = 0;
9    for (int[] e : g[u]) {
10        int v = e[0], id = e[1];
11        if (id == parentEdge) continue;
12        if (tin[v] == 0) {
13            children++;
14            edgeStack.push(id);                       // tree edge goes on the edge stack
15            dfs(g, v, id);
16            low[u] = Math.min(low[u], low[v]);
17            if (low[v] >= tin[u]) {                   // v's subtree cannot get above u: u separates it
18                if (parentEdge != -1) cut[u] = true;  // root is judged separately below
19                List<Integer> block = new ArrayList<>();
20                int x;
21                do { x = edgeStack.pop(); block.add(x); } while (x != id);
22                blocks.add(block);                    // pop one biconnected block
23            }
24        } else if (tin[v] < tin[u]) {                 // back edge to an ancestor: push it once, from its lower end
25            edgeStack.push(id);
26            low[u] = Math.min(low[u], tin[v]);
27        }
28    }
29    if (parentEdge == -1 && children >= 2) cut[u] = true;   // the root is a cut vertex only with two or more DFS children
30}

Live state

0 cut vertices0 blocks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L1	n=5 edges=6	An articulation point (cut vertex) is a vertex whose removal splits its component. For a non-root u with DFS child v the test is low[v] ≥ tin[u] (v's subtree cannot climb above u). The DFS root is special: it is a cut vertex only if it has two or more children. DFS root: 0.
2	L1	root=0	0 has not been visited: it becomes the root of a new DFS tree.
3	L7	u=0 tin=1	Enter 0: tin = low = 1.
4	L14	u=0 v=1 children=1	Tree edge 0-1: push it on the edge stack and go down into 1. 0 now has 1 DFS child.
5	L7	u=1 tin=2	Enter 1: tin = low = 2.
6	L11	u=1 edge=0-1	Skip 0-1: the edge used to reach 1.
7	L14	u=1 v=2 children=1	Tree edge 1-2: push it on the edge stack and go down into 2. 1 now has 1 DFS child.
8	L7	u=2 tin=3	Enter 2: tin = low = 3.
9	L11	u=2 edge=1-2	Skip 1-2: the edge used to reach 2.
10	L24	u=2 v=0 low=1	2-0 is a back edge up to 0: push it on the edge stack once, from its lower end. low[2] drops from 3 to 1.
11	L14	u=2 v=3 children=1	Tree edge 2-3: push it on the edge stack and go down into 3. 2 now has 1 DFS child.
12	L7	u=3 tin=4	Enter 3: tin = low = 4.
13	L11	u=3 edge=2-3	Skip 2-3: the edge used to reach 3.
14	L14	u=3 v=4 children=1	Tree edge 3-4: push it on the edge stack and go down into 4. 3 now has 1 DFS child.
15	L7	u=4 tin=5	Enter 4: tin = low = 5.
16	L11	u=4 edge=3-4	Skip 3-4: the edge used to reach 4.
17	L24	u=4 v=2 low=3	4-2 is a back edge up to 2: push it on the edge stack once, from its lower end. low[4] drops from 5 to 3.
18	L29	u=4	4 is finished.
19	L17	u=3 v=4 low_v=3 tin_u=4	low[4] = 3 < tin[3] = 4: 4's subtree has a back edge above 3, so 3 does not separate it. low[3] drops from 4 to 3.
20	L29	u=3	3 is finished.
21	L22	u=2 v=3 block={2,3,4}	low[3] = 3 ≥ tin[2] = 3: 3's subtree cannot get above 2. 2 is an articulation point. Pop the edge stack down to 2-3: block B1 = {2,3,4}.
22	L12	u=2 v=4	4 is a younger finished vertex: 4-2 was already pushed from 4's side.
23	L29	u=2	2 is finished.
24	L17	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 < tin[1] = 2: 2's subtree has a back edge above 1, so 1 does not separate it. low[1] drops from 2 to 1.
25	L29	u=1	1 is finished.
26	L22	u=0 v=1 block={0,1,2}	low[1] = 1 ≥ tin[0] = 1: 1's subtree cannot get above 0. 0 is the root: this alone proves nothing; it counts only if it gets a second child. Pop the edge stack down to 0-1: block B2 = {0,1,2}.
27	L12	u=0 v=2	2 is a younger finished vertex: 2-0 was already pushed from 2's side.
28	L29	u=0 children=1	0 is the root with 1 DFS child: fewer than two, so removing it leaves the rest connected: not an articulation point, even though every child satisfied low ≥ tin.
29	L29	return=1 cut_vertices={2} blocks=2	1 articulation point {2} and 2 blocks. The block-cut tree has a node per block and per cut vertex (3) and joins each cut vertex to the blocks containing it (2 links).

38.03.4

Block-cut tree

Make a node for every block and for every cut vertex, and join a cut vertex to each block that contains it. The result is the **block-cut tree** (a forest for a disconnected graph). It is a tree because a cycle in it would mean a cycle through several blocks, which would merge them into one block.

It summarises the cut structure: leaves are blocks with exactly one cut vertex, and the path between two blocks lists the cut vertices that separate them. For the “Two triangles joined by an edge” preset there are 3 blocks (two triangles and the connecting edge 2-3), 2 cut vertices (2 and 3) and 4 links, so 5 nodes and 4 edges.

The code recovers the vertices of each block from its edge ids and keeps a link {cutVertex, blockIndex} whenever a block contains a cut vertex.

Java

1static List<int[]> blockCutTree(int n, int[][] edges) {   // links {cut vertex, block index}
2    List<List<Integer>> blocks = biconnectedBlocks(n, edges);
3    boolean[] cut = articulationPoints(n, edges);
4    List<int[]> links = new ArrayList<>();
5    for (int b = 0; b < blocks.size(); b++) {
6        Set<Integer> vertices = new TreeSet<>();
7        for (int id : blocks.get(b)) { vertices.add(edges[id][0]); vertices.add(edges[id][1]); }
8        for (int v : vertices) if (cut[v]) links.add(new int[]{v, b});
9    }
10    return links;
11}

Articulation points, the root exception, biconnected blocks

Interactive · edit the input

node caption: tin / low; edge colour = block · 5 vertices · 6 edges

Current vertex or edgeTree edge or finished vertexBack edge or open vertexArticulation point

tin

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

edge stack (top on the right)

empty

blocks (vertex sets)

none yet

Setup

Step 1 / 29

Java

1static int timer = 0;
2static int[] tin, low;
3static boolean[] cut;                                 // cut[v]: v is an articulation point
4static Deque<Integer> edgeStack = new ArrayDeque<>();
5static List<List<Integer>> blocks = new ArrayList<>();   // each block as a list of edge ids
6static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
7    tin[u] = low[u] = ++timer;
8    int children = 0;
9    for (int[] e : g[u]) {
10        int v = e[0], id = e[1];
11        if (id == parentEdge) continue;
12        if (tin[v] == 0) {
13            children++;
14            edgeStack.push(id);                       // tree edge goes on the edge stack
15            dfs(g, v, id);
16            low[u] = Math.min(low[u], low[v]);
17            if (low[v] >= tin[u]) {                   // v's subtree cannot get above u: u separates it
18                if (parentEdge != -1) cut[u] = true;  // root is judged separately below
19                List<Integer> block = new ArrayList<>();
20                int x;
21                do { x = edgeStack.pop(); block.add(x); } while (x != id);
22                blocks.add(block);                    // pop one biconnected block
23            }
24        } else if (tin[v] < tin[u]) {                 // back edge to an ancestor: push it once, from its lower end
25            edgeStack.push(id);
26            low[u] = Math.min(low[u], tin[v]);
27        }
28    }
29    if (parentEdge == -1 && children >= 2) cut[u] = true;   // the root is a cut vertex only with two or more DFS children
30}

Live state

0 cut vertices0 blocks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L1	n=5 edges=6	An articulation point (cut vertex) is a vertex whose removal splits its component. For a non-root u with DFS child v the test is low[v] ≥ tin[u] (v's subtree cannot climb above u). The DFS root is special: it is a cut vertex only if it has two or more children. DFS root: 0.
2	L1	root=0	0 has not been visited: it becomes the root of a new DFS tree.
3	L7	u=0 tin=1	Enter 0: tin = low = 1.
4	L14	u=0 v=1 children=1	Tree edge 0-1: push it on the edge stack and go down into 1. 0 now has 1 DFS child.
5	L7	u=1 tin=2	Enter 1: tin = low = 2.
6	L11	u=1 edge=0-1	Skip 0-1: the edge used to reach 1.
7	L14	u=1 v=2 children=1	Tree edge 1-2: push it on the edge stack and go down into 2. 1 now has 1 DFS child.
8	L7	u=2 tin=3	Enter 2: tin = low = 3.
9	L11	u=2 edge=1-2	Skip 1-2: the edge used to reach 2.
10	L24	u=2 v=0 low=1	2-0 is a back edge up to 0: push it on the edge stack once, from its lower end. low[2] drops from 3 to 1.
11	L14	u=2 v=3 children=1	Tree edge 2-3: push it on the edge stack and go down into 3. 2 now has 1 DFS child.
12	L7	u=3 tin=4	Enter 3: tin = low = 4.
13	L11	u=3 edge=2-3	Skip 2-3: the edge used to reach 3.
14	L14	u=3 v=4 children=1	Tree edge 3-4: push it on the edge stack and go down into 4. 3 now has 1 DFS child.
15	L7	u=4 tin=5	Enter 4: tin = low = 5.
16	L11	u=4 edge=3-4	Skip 3-4: the edge used to reach 4.
17	L24	u=4 v=2 low=3	4-2 is a back edge up to 2: push it on the edge stack once, from its lower end. low[4] drops from 5 to 3.
18	L29	u=4	4 is finished.
19	L17	u=3 v=4 low_v=3 tin_u=4	low[4] = 3 < tin[3] = 4: 4's subtree has a back edge above 3, so 3 does not separate it. low[3] drops from 4 to 3.
20	L29	u=3	3 is finished.
21	L22	u=2 v=3 block={2,3,4}	low[3] = 3 ≥ tin[2] = 3: 3's subtree cannot get above 2. 2 is an articulation point. Pop the edge stack down to 2-3: block B1 = {2,3,4}.
22	L12	u=2 v=4	4 is a younger finished vertex: 4-2 was already pushed from 4's side.
23	L29	u=2	2 is finished.
24	L17	u=1 v=2 low_v=1 tin_u=2	low[2] = 1 < tin[1] = 2: 2's subtree has a back edge above 1, so 1 does not separate it. low[1] drops from 2 to 1.
25	L29	u=1	1 is finished.
26	L22	u=0 v=1 block={0,1,2}	low[1] = 1 ≥ tin[0] = 1: 1's subtree cannot get above 0. 0 is the root: this alone proves nothing; it counts only if it gets a second child. Pop the edge stack down to 0-1: block B2 = {0,1,2}.
27	L12	u=0 v=2	2 is a younger finished vertex: 2-0 was already pushed from 2's side.
28	L29	u=0 children=1	0 is the root with 1 DFS child: fewer than two, so removing it leaves the rest connected: not an articulation point, even though every child satisfied low ≥ tin.
29	L29	return=1 cut_vertices={2} blocks=2	1 articulation point {2} and 2 blocks. The block-cut tree has a node per block and per cut vertex (3) and joins each cut vertex to the blocks containing it (2 links).

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

Non-root cut vertex: low[v] >= tin[u] for some child v. Root: two or more DFS children.
Bridges use > and cut vertices use >=: same arrays, one character apart.
An edge stack pops one block each time a cut test succeeds; blocks and cut vertices form the block-cut tree.