1732. How Many Critical Junctions
An UNDIRECTED graph has n vertices and m edges. A vertex is a CRITICAL
JUNCTION when deleting it, along with every edge touching it, leaves more
connected pieces among the REMAINING vertices than there were before.
Print how many critical junctions there are. Such a vertex is usually called an ARTICULATION POINT.
1-2, 2-3 -> 1 vertex 2
1-2, 2-3, 3-1 -> 0 the cycle protects everything
1-2, 2-3, 3-1, 3-4, 4-5 -> 2 vertices 3 and 4
star centred at 2 -> 1 vertex 2
1 vertex, no edges -> 0
Deleting a vertex of degree 1 never counts: the rest stays in one piece, and one piece is not more than one piece. Deleting an isolated vertex REDUCES the count, which is also not an increase.
## The three things that have to be said
directed? no.
self-loops? allowed, and irrelevant: an edge from v to v joins nothing.
parallel edges? allowed, and irrelevant here. This is the sharpest contrast
with problem 1729: two copies of an edge stop it being a
bridge, and change nothing about whether either endpoint is
a critical junction.
disconnected? allowed. A critical junction in one piece is still critical.
## What most people try first
The definition: delete each vertex, count the pieces, compare. Correct, this is
what the oracle does, and it costs O(n(n + m)), which at n = m = 200000 is
8 * 10^10 steps.
The second attempt is to reuse problem 1729 and call the endpoints of every bridge critical. That is wrong in BOTH directions, which is worth seeing:
1-2 alone vertex 1 is the endpoint of a bridge and is not critical
two triangles
sharing vertex 3 no edge is a bridge and vertex 3 IS critical
Both of those are tests below. Bridges and critical junctions are genuinely different questions.
## The test, with the root as a separate case
Run problem 1728's search and use the low-link values.
``` v is NOT a root of the search: v is critical <=> some search-tree child c of v has low[c] >= tin[v]
v IS a root of the search: v is critical <=> v has TWO OR MORE search-tree children ```
## Why a non-root vertex uses that test
Deleting v detaches the subtree of a child c exactly when nothing in that
subtree has an edge to a proper ancestor of v. Since an undirected search has
no cross edges, the only escapes from c's subtree avoiding v are edges to
ancestors, and low[c] is the earliest entry time they reach. So
low[c] >= tin[v] says no escape above v exists and the subtree falls off,
while low[c] < tin[v] says one does and it stays attached through v's own
ancestors.
Note the inequality is NOT strict, unlike the bridge test. low[c] == tin[v]
means the subtree can climb back to v itself and no further, which does not
help when v is the vertex being deleted. That one character is the entire
difference between this problem and problem 1729.
## Why the root is different
A root has no ancestors, so there is no "rest of the graph above it" for a child subtree to stay attached to. Every child subtree of the root is joined to the others only through the root itself, since a cross edge between two of them would have made them one subtree. So deleting the root leaves exactly one piece per child:
0 children deleting it removes an isolated vertex, pieces go DOWN
1 child one piece remains, which is not an increase
2 or more two or more pieces, so it is critical
Applying the non-root test to a root is the single most common error here, and
it reports every root with one child as critical. On a path 1-2-3 searched
from vertex 1, the child 2 has low[2] = tin[2] > tin[1], so the non-root test
would fire on vertex 1, which is not critical. The path test below catches that.
## Cost
Time O(n + m log m), 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 1733 prints which vertices they are and problem 1734 asks how much damage the worst one does. Problem 1729 is the edge version, and problem 1736 counts the pieces the critical junctions cut the graph into.
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
Input
The first line contains two integers n and m, the number of vertices and the number of edges.
Each of the next m lines contains two integers u and v, an undirected edge joining u and v.
Output
Print one integer on its own line: the number of vertices whose removal, together with the edges touching them, would leave more connected pieces among the remaining vertices than the graph has now. Print 0 when there are none. Print no other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.