1733. Which Junctions Are Critical

An UNDIRECTED graph has n vertices and m edges. Print, in increasing order, every vertex whose removal, together with the edges touching it, would leave MORE connected pieces among the remaining vertices than the graph has now. Print None if there are none.

1-2, 2-3 -> 2 1-2, 2-3, 3-1 -> None 1-2, 2-3, 3-1, 3-4, 4-5 -> 3 4 star centred at 2 -> 2

Such a vertex is called an ARTICULATION POINT, and the set of them is the answer to "which single machine failure would split the network".

## Why the list is sorted

The search finds these vertices in the order it finishes them, which depends on which vertex it started at and in what order it took the edges. Two correct implementations would disagree. Sorting makes the output a property of the graph and not of the search, which is also why no search order needs pinning here.

## The three things that have to be said

directed? no. self-loops? allowed, and they join nothing, so they never matter. parallel edges? allowed, and unlike with bridges they change nothing at all. disconnected? allowed, and this problem has a trap there: the search restarts at every unentered vertex, and EVERY one of those restarts is a root with its own rule.

## What most people try first

Deleting each vertex and recounting, which is O(n(n + m)) and at n = m = 200000 is 8 * 10^10 steps.

The second attempt, having solved problem 1729, is to print the endpoints of every bridge. That is wrong in both directions: a single edge 1-2 is a bridge and neither end is critical, while two triangles sharing one vertex have no bridge at all and that shared vertex is critical. Both are tests below.

## The test

v is NOT a root: critical <=> some tree child c of v has low[c] >= tin[v] v IS a root: critical <=> v has TWO OR MORE tree children

Collect the vertices that pass, then sort.

For a non-root v, deleting it detaches a child subtree exactly when nothing in that subtree reaches a proper ancestor of v. An undirected depth-first search has no cross edges, so the only escapes from that subtree are the tree edge through v and edges to ancestors, and low[c] is the earliest entry time those reach. The inequality is NOT strict: low[c] == tin[v] means the subtree can climb back to v and no further, which is useless once v is gone.

## Why every root needs the other rule, in every component

A root has no ancestors, so there is nothing above it to keep a child subtree attached. Different child subtrees of a root are joined only through the root, because a cross edge between two of them cannot exist. So the pieces left after deleting a root number exactly its tree children: zero children means an isolated vertex and the count goes down, one child means one piece and no increase, two or more means it is critical.

The disconnected case is where this bites hardest. A search over a graph with three components has THREE roots, and each must be judged by the child-count rule rather than the low-link rule. A solution that treats only vertex 1 as a root has no parent recorded for the other starting vertices at all. The disconnected test below is built for that.

## Cost

Time O(n + m log m), the sort being the only part above linear. Space O(n + m). The search is ITERATIVE: a path of 200000 vertices is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

## Related

Problem 1732 is the count. Problem 1734 asks how many pieces the worst single removal leaves. Problem 1730 is the edge version, and problem 1736 counts the blocks these vertices separate.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected