1736. How Many Pieces Have No Critical Junction

An UNDIRECTED graph has n vertices and m edges. Say two edges BELONG TOGETHER when some cycle that uses no edge twice contains both of them. Every edge belongs together with itself, and the relation turns out to split the edges into groups, called BLOCKS or biconnected components.

Print how many blocks there are. An edge belonging to no cycle at all forms a block by itself.

1-2, 2-3, 3-1 -> 1 the triangle is one block 1-2, 2-3 -> 2 neither edge is on a cycle 1-2, 1-2 -> 1 the two copies form a cycle of length two 1-2, 2-3, 3-1, 3-4 -> 2 the triangle, and the lone edge 3-4 two triangles sharing vertex 3 -> 2 1 vertex, no edges -> 0

The answer is 0 exactly when m is 0, since every edge is in some block.

## Why this is a different number from problem 1735

Problem 1735 asks what survives when any single EDGE fails, and two triangles sharing a vertex survive that as one piece: no edge of either triangle is a bridge. This problem separates at VERTICES, and the shared vertex is exactly where the two triangles come apart. Same graph, answers 1 and 2. The blocks are the pieces that have no critical junction inside them, which is why problem 1733's test reappears here.

## The three things that have to be said

directed? no. self-loops? allowed, and a self-loop IS a cycle using no edge twice, so it is a block all by itself. parallel edges? allowed, and two copies of one edge form a cycle of length two, so they share a block. disconnected? allowed, and the blocks of each piece are counted together.

## What most people try first

Counting connected pieces, which is the wrong relation entirely: a path of three vertices is one piece and two blocks.

The second attempt is to count the critical junctions and add one, from problem 1732. That works on a path and fails on a star: a star with four arms has one critical junction and four blocks.

The honest brute force is to enumerate the cycles, which is what this problem's oracle does on graphs of six vertices, and it is exponential.

## One search, and a test you have already written

blocks = #{ v with a parent : low[v] >= tin[par[v]] } + #{ self-loops }

That is the SAME inequality as problem 1732's critical-junction test, used to count something else.

## Why counting those tree edges counts the blocks

Take any block other than a lone self-loop. Among its vertices, let x be the one entered first by the search. Claim: the block contains exactly one tree edge whose lower end v satisfies low[v] >= tin[x] and whose upper end is x.

Every other vertex of the block is reachable from x by a path inside the block, and the search explores it before x finishes, so the whole block lies in x's subtree. Now x may have several tree children, but only the children whose subtrees contain the rest of THIS block count, and there is exactly one: if two children c1 and c2 both held part of the block, then a cycle through both would have to pass through x, and a cycle visiting x once cannot enter and leave through two different children and still return, so one of them would force x to be visited twice.

For that single child v, nothing in the block below x escapes above x, or the block would extend further up, so low[v] >= tin[x]. And for any child of any vertex strictly inside the block, the subtree can climb back past its parent, giving low < tin[parent], so no other tree edge of the block is counted.

So blocks correspond one to one with the counted tree edges, except for self-loops, which the search skips and which are therefore added separately.

## Cost

Time O(n + m log m), space O(n + m), one search and two counters. 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 uses the identical inequality to find critical junctions. Problem 1735 is the edge-failure analogue and gives a different number. Problem 1739 asks whether every block is a single edge or a single cycle.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur, and a self-loop is a cycle on its own - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected