Single Points of Failure — Solution & Editorial

Back to the Problem

Lowlink again, with the two classic cases: a non-root u is critical if some child's low ≥ disc[u]; a DFS root is critical iff it has ≥ 2 DFS children. (Note the parent-skip here is by node, unlike bridges.)

Complexity: O(N + M)

Watch out: The root rule (≥ 2 DFS children) is separate from the low ≥ disc rule — most wrong answers forget one.