AlgoScope

Articulation Points

A vertex is an articulation point when some DFS child has low[v] >= disc[u], or it is the root with two subtrees.

Connectivity and topological order, algorithm, advanced
Back edge 2 to 0, low of 2 is 0.0011203456u
Back edge 2 to 0, low of 2 is 0.0011203456u

Bridges and Components: Articulation points

Decision, step 5 of 19

Edge 2-0 leads to a vertex seen at time 0, an ancestor on the current path. That is earlier than low[2] = 2, so low[2] becomes 0: 2 can climb to 0.

How bridges and components works

Cost

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

Before this

Taught by the same lesson

Bridges and Components covers these too, in the same run.