Articulation Points
An interactive, step-by-step visualisation of Articulation Points.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
same DFS as bridges, tracking disc/low root with 2+ children ⇒ articulation point non-root: child low[v] ≥ disc[u] ⇒ articulation point
Reference implementation
# same disc/low DFS as Bridges, different test:
if is_root and children > 1: is_ap[u] = True
if not is_root and low[v] >= disc[u]: is_ap[u] = True