Graph Theory37 sections · 1633 units
Open in Course

Articulation Points - Core idea

Apply Tarjan's vertex algo

Use Tarjan's algorithm with the articulation point condition: a vertex uu is an articulation point if it is the root with 2\geq 2 children, or a non-root with a child vv where low[v] >= disc[u]. The difference from bridges: \geq instead of >>.

A vertex is critical if its subtree cannot escape beyond it. Time complexity: O(V+E)O(V+E), same as the bridge algorithm. You compute the same low-link values but check different conditions.