Graph AlgosAlgorithmaka cut vertices, biconnected components

Articulation Points

Find every vertex of an undirected graph whose removal disconnects it, via DFS low-link values with a special rule for the root.

▶ VisualizePattern: Depth-First SearchPractice (1)
Progress

Overview

An articulation point (cut vertex) is a vertex whose removal — together with its incident edges — increases the number of Connected Components. A graph with no articulation points (and at least 3 vertices) is biconnected: any two vertices lie on a common cycle.

The algorithm is the vertex analogue of Bridges: DFS with discovery times disc[u] and low-link values low[u]. A non-root vertex u is an articulation point if it has some DFS child v with low[v] >= disc[u] — the subtree of v cannot reach *above* u without passing through u. The root of the DFS tree is special: it is an articulation point iff it has two or more DFS children.

Unlike bridges, one vertex can be reported by several children; collect into a boolean array, not a list, to avoid duplicates. The blocks between articulation points are the biconnected components, which can be extracted with an edge stack in the same DFS.

undirectedlow-linkDFScut vertexbiconnectivityO(V + E)

Intuition

A mental model before the formal terms.

Think of the DFS tree as a hanging mobile. Pinch a vertex u and lift it out. Each child subtree stays attached to the rest only if it has a rope (back edge) tied *strictly above* u. If some child subtree's highest rope reaches only u itself or lower — low[v] >= disc[u] — that subtree drops off. Note the >=: a rope tied to u does not help, because u is the thing being removed. For bridges it was > because there the edge, not u, was being removed and reaching u was enough.

The root has no "above", so the rule degenerates: it is a cut vertex only if it holds two separate child subtrees together, i.e. has at least two DFS children.

Example: edges 0—1, 1—2, 2—0, 2—3. DFS from 0: disc = [0, 1, 2, 3]. low[3] = 3 >= disc[2] = 2 → 2 is an articulation point (removing it strands 3). low[2] = 0 (back edge to 0), so low[2] < disc[1] → 1 is not. Root 0 has one DFS child (1) → not an articulation point.

How it works

  1. Initialise disc[v] = -1, timer t = 0, isCut[v] = false.
  2. dfs(u, parent): disc[u] = low[u] = t++; children = 0. For each neighbour v: if v == parent, skip (for multigraphs skip only the one edge you came along). If v undiscovered: children++, dfs(v, u), low[u] = min(low[u], low[v]); if parent != -1 and low[v] >= disc[u], mark isCut[u]. Else: low[u] = min(low[u], disc[v]).
  3. After the loop, if parent == -1 and children > 1, mark isCut[u] (root rule).
  4. Run dfs(s, -1) from every undiscovered vertex s.

Why it works

Removing a non-root u separates a child subtree T(v) from the rest iff T(v) has no back edge to a proper ancestor of u. Since all non-tree edges in an undirected DFS are back edges to ancestors, "escaping" means reaching a discovery time < disc[u]. low[v] is the minimum reachable, so low[v] >= disc[u] ⇔ no escape ⇔ u is a cut vertex. Ancestors of u and the other subtrees remain connected through the tree, so this is the only way the count of components can rise.

For the root, every child subtree is separated from every other child subtree when the root is removed (a back edge from one child subtree can only go to an ancestor — which is the root itself). So with ≥ 2 children the root is a cut vertex, and with ≤ 1 child its removal leaves a connected tree.

Same DFS as bridges: O(V + E).

Recognition

How to tell a problem wants this.

  • "Which server / person / junction, if removed, splits the network?" — vertex removal, undirected graph.
  • "Is the network resilient to any single node failure?" — check for zero articulation points.
  • Biconnected components, block-cut tree, "cactus" graph structure questions.
“connected groups” → Depth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDEFG
Articulation points
empty
1/23An articulation point is a node whose removal disconnects the graph. One DFS with discovery times and low-links finds all of them in O(V + E).
Current node (label = disc/low)On recursion pathFinishedDFS tree edgeBack edgeArticulation point
PseudocodeLearn Articulation Points →
1time = 0
2def dfs(u, parent):
3  disc[u] = low[u] = time; time += 1
4  for v in neighbors(u), skipping parent:
5    if v unvisited: dfs(v, u); low[u] = min(low[u], low[v])
6      if parent != None and low[v] >= disc[u]: u is an articulation point
7    else: low[u] = min(low[u], disc[v])   # back edge
8  if parent == None and tree children >= 2: root u is an articulation point
9for u in nodes: if u unvisited: dfs(u, None)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1disc[*] = -1; t = 0; isCut[*] = false
2dfs(u, parent):
3  disc[u] = low[u] = t++; children = 0
4  for v in adj[u]:
5    if v == parent: continue
6    if disc[v] == -1:
7      children++; dfs(v, u); low[u] = min(low[u], low[v])
8      if parent != -1 and low[v] >= disc[u]: isCut[u] = true
9    else: low[u] = min(low[u], disc[v])
10  if parent == -1 and children > 1: isCut[u] = true

Implementations

1def articulation_points(adj: list[list[int]]) -> list[int]:
2    """An articulation point (cut vertex) is a vertex whose removal increases
3    the number of connected components. Tarjan's rule, same disc/low machinery
4    as bridges but with two cases:
5      - non-root u is a cut vertex iff some child v has low[v] >= disc[u]
6      - the root is a cut vertex iff it has two or more DFS children"""
7    n = len(adj)
8 
91 · disc, low, and a flag list for the answer
10    disc = [-1] * n
11    low = [0] * n
12    is_cut = [False] * n
13    timer = 0
14 
15    for s in range(n):
16        if disc[s] != -1:
17            continue
18        root_children = 0
19 
202 · Frames carry the vertex, its DFS parent, and a neighbour cursor
21        stack = [[s, -1, 0]]  # [vertex, parent, neighbour cursor]
22        disc[s] = low[s] = timer
23        timer += 1
24 
25        while stack:
26            f = stack[-1]
27            u, parent, i = f[0], f[1], f[2]
28            if i < len(adj[u]):
29                f[2] += 1
30                v = adj[u][i]
31                if v == parent:
32                    continue  # the edge we arrived on
33                if disc[v] == -1:
34                    if u == s:
35                        root_children += 1
36                    disc[v] = low[v] = timer
37                    timer += 1
38                    stack.append([v, u, 0])
39                else:
40                    low[u] = min(low[u], disc[v])  # back edge
41            else:
423 · Unwinding: propagate low, then test the non-root rule
43                stack.pop()
44                if stack:
45                    p = stack[-1][0]
46                    low[p] = min(low[p], low[u])
47                    if p != s and low[u] >= disc[p]:
48                        is_cut[p] = True
49 
504 · The root is special: it cuts only if the DFS branched twice
51        if root_children >= 2:
52            is_cut[s] = True
53 
545 · Collect the flagged vertices
55    return [v for v in range(n) if is_cut[v]]
Walkthrough
  1. Frames are mutable three-element lists so f[2] += 1 advances the cursor in place.
  2. u, parent, i = f[0], f[1], f[2] unpacks the frame at the top of each iteration for readability.
  3. The >= in low[u] >= disc[p] is the cut-vertex rule, distinct from the bridge rule's >.
  4. root_children is reset per component because it is declared inside the outer for s loop.
  5. The final list comprehension collects the flagged vertices in one expression.
Complexity (this implementation)
time O(V + E) — one DFS, each edge examined twice · space O(V)
Language notes
  • networkx.articulation_points(G) yields them directly, and networkx.biconnected_components(G) gives the related decomposition.
  • A tuple frame would raise TypeError on the cursor increment, hence the list.
  • The list comprehension [v for v in range(n) if is_cut[v]] is idiomatic; list(compress(range(n), is_cut)) from itertools is the faster C-level equivalent.
  • The iterative form avoids RecursionError, which a recursive Tarjan reaches on a path of about 1000 vertices.
Common mistakes in this language
  • Declaring root_children outside the component loop, so it accumulates and misreports later roots.
  • Using > instead of >=, computing bridge endpoints rather than cut vertices.
  • Using a tuple frame and hitting TypeError on the increment.
Language differences that matter here
  • The algorithm is identical in all four; the only structural difference is how the DFS frame is mutated — C++ indexes the stack to avoid reference invalidation, JS/TS mutate a heap object, and Python mutates a list.
  • C++ is again the only language where the frame reference can be invalidated by a push, which is why this version indexes stack[depth] rather than binding back().
  • Library support: networkx.articulation_points in Python and Boost.Graph articulation_points in C++; nothing in JS/TS.
  • Collecting the flagged vertices: a C++ loop, a JS/TS loop or flatMap, and a Python list comprehension (or itertools.compress) — the same operation with increasingly compact spellings.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Same DFS as bridge-finding; both can be computed in one pass.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Single-node-failure analysis of undirected networks.
  • Building the block-cut tree / biconnected components for structural questions.
  • Checking biconnectivity (no cut vertices and connected).
Avoid it when
  • Edge removal questions — use Bridges (> instead of >=, no root rule).
  • Directed graphs — vertex-cut reachability there needs dominator trees or SCC reasoning.
  • "Remove k vertices" for k ≥ 2 — vertex connectivity in general needs max-flow.

Alternatives

BridgesConnected ComponentsTarjan's SCC Algorithm

Common mistakes

  • Using > instead of >= — a child whose subtree reaches exactly u still gets cut off when u is removed.
  • Applying the low[v] >= disc[u] rule to the root — a root with one child would be misreported. The root needs the child-count rule.
  • Counting children from the neighbour list instead of from *DFS tree* children (only count when disc[v] == -1 before recursing).
  • Pushing u into a result list every time the condition fires, producing duplicates; use a boolean array.
  • Updating low[u] from low[v] for back edges (should be disc[v]).

Interview patterns

  • Find all cut vertices, then answer "is the network resilient to one node failure".
  • Biconnected components via an edge stack popped whenever low[v] >= disc[u].
  • Explain the difference between the > (bridge) and >= (articulation) conditions and the root special case — a classic interview probe.
Interview questions on this
Mock interviews

Example problems

Critical Connections in a Networkhard