Pattern visualizer
Articulation Points in Graph
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. 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..
Tarjan's low-link DFS: a cut vertex is one no child subtree can climb past
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.
1FUNCTION findArticulationPoints(n, adj):2 tin, low <- ARRAY of -1, size n; timer <- 0; ans <- EMPTY SET3 FUNCTION dfs(u, parent, children):4 tin[u] <- timer; low[u] <- timer; timer <- timer + 15 FOR EACH v IN adj[u]6 IF v = parent: CONTINUE7 IF tin[v] != -1: low[u] <- MIN(low[u], tin[v])8 ELSE9 dfs(v, u); low[u] <- MIN(low[u], low[v]); children <- children + 110 IF parent != -1 AND low[v] >= tin[u]: ADD u TO ans11 IF parent = -1 AND children > 1: ADD u TO ans12 dfs(0, -1, 0)13 RETURN ans
← / → step · space play · Home restart