DSA Tracker

Visualize

Articulation Point

Tarjan's low-link DFS: a cut vertex is one no child subtree can climb past

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

Run one DFS and give every node two numbers: tin, the order it was first reached, and low, the earliest tin reachable from its subtree using at most one back edge. A non-root node u is an articulation point the moment some child v cannot climb back past u — low[v] >= tin[u] — because then u is the only link holding that child's subtree to the rest of the graph. The root is a special case: it has no ancestor to climb toward, so it is a cut vertex only if the DFS had to start two or more separate child branches from it.

Details

Animated on: n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]] (undirected, connected) — find every node whose removal disconnects the graph.

Problem:Articulation PointHard

Tarjan's low-link DFS: a cut vertex is one no child subtree can climb past

step 1 / 15

Undirected connected graph

5 nodes, 5 edges. A node is an articulation point if deleting it splits the graph into more pieces. One DFS finds every one: track how far back up the tree each subtree can still reach.

Pseudocode
1FUNCTION findArticulationPoints(n, adj):
2  tin, low <- ARRAY of -1, size n; timer <- 0; ans <- EMPTY SET
3  FUNCTION dfs(u, parent, children):
4    tin[u] <- timer; low[u] <- timer; timer <- timer + 1
5    FOR EACH v IN adj[u]
6      IF v = parent: CONTINUE
7      IF tin[v] != -1: low[u] <- MIN(low[u], tin[v])
8      ELSE
9        dfs(v, u); low[u] <- MIN(low[u], low[v]); children <- children + 1
10        IF parent != -1 AND low[v] >= tin[u]: ADD u TO ans
11    IF parent = -1 AND children > 1: ADD u TO ans
12  dfs(0, -1, 0)
13  RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. 5 nodes, 5 edges. A node is an articulation point if deleting it splits the graph into more pieces. One DFS finds every one: track how far back up the tree each subtree can still reach.
  2. Enter 0 — the DFS root: tin[0] = low[0] = 0, the order it was first reached.
  3. Enter 1 from 0: tin[1] = low[1] = 1, the order it was first reached.
  4. Enter 2 from 1: tin[2] = low[2] = 2, the order it was first reached.
  5. 0 is already visited and isn't 2's parent, so 2-0 is a BACK EDGE reaching an ancestor: low[2] = min(2, tin[0]=0) = 0.
  6. Back at 1 after finishing child 2: low[1] = min(1, low[2]=0) = 0.
  7. Enter 3 from 1: tin[3] = low[3] = 3, the order it was first reached.
  8. Enter 4 from 3: tin[4] = low[4] = 4, the order it was first reached.
  9. Back at 3 after finishing child 4: low[3] = min(3, low[4]=4) = 3.
  10. low[4]=4 >= tin[3]=3, so 4's subtree has no edge back above 3 — removing 3 would strand it. Mark 3.
  11. Back at 1 after finishing child 3: low[1] = min(0, low[3]=3) = 0.
  12. low[3]=3 >= tin[1]=1, so 3's subtree has no edge back above 1 — removing 1 would strand it. Mark 1.
  13. Back at 0 after finishing child 1: low[0] = min(0, low[1]=0) = 0.
  14. 2 is already visited and isn't 0's parent, so 0-2 is a BACK EDGE reaching an ancestor: low[0] = min(0, tin[2]=2) = 0.
  15. DFS is done. RETURN [1, 3] — removing either one increases the number of connected pieces.

Now solve it yourself

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

Solve Articulation Point in the editorAll Graph problemsBack to roadmap