1735. What Survives Every Single Link Failure
An UNDIRECTED graph has n vertices and m edges. Delete EVERY bridge at once,
where a bridge is an edge whose single removal would disconnect something, and
print how many connected pieces are left.
Those pieces are the TWO-EDGE-CONNECTED COMPONENTS: inside one of them, any two vertices stay joined however one edge fails.
1-2, 2-3 -> 3 both edges go; three lone vertices
1-2, 2-3, 3-1 -> 1 no bridge goes; the triangle survives
1-2, 2-3, 3-1, 3-4 -> 2 {1,2,3} and {4}
1-2, 1-2 -> 1 neither copy is a bridge
1-2, 3-4 -> 4 both bridges go
Every vertex ends up in exactly one piece, including vertices the deletions
isolate, so the answer is between 1 and n.
## The three things that have to be said
directed? no.
self-loops? allowed, never a bridge, and never joins two vertices, so
they never change the answer.
parallel edges? allowed, and they protect each other, so a repeated edge
survives and KEEPS its endpoints in one piece.
disconnected? allowed, and each piece of the input contributes its own
two-edge-connected pieces.
## What most people try first
Finding the bridges, physically building the graph without them, and running a fresh search to count components. That is correct and it is two passes plus an extra copy of the graph, which is more work and more code than needed.
The genuinely wrong attempt is to count the pieces with no bridge inside them, forgetting the vertices that bridges leave stranded. On a path of three vertices every edge is a bridge, so there is nothing left but three isolated vertices, and a solution counting "pieces containing at least one surviving edge" answers 0.
## One formula, no second search
answer = (number of connected pieces of the input) + (number of bridges)
The argument is short and worth keeping. Deleting a bridge from a connected graph leaves exactly two pieces, by the definition of a bridge: it disconnects something, and it cannot leave three pieces, because every vertex still reaches one of the bridge's two endpoints along a path that did not use the bridge.
So each bridge deleted raises the piece count by exactly one. And an edge that was not a bridge before the deletions is still not a bridge after them: it lies on a cycle, and that cycle contains no bridges at all, since an edge on a cycle is never a bridge, so the whole cycle survives. Hence the deletions can be done in any order, each adding one, and the total is the starting count plus the number of bridges.
## Where this is used
The pieces are the nodes of the BRIDGE TREE, which problem 1737 measures. Contracting each piece to a point leaves a forest whose edges are exactly the bridges, and many questions about "what survives one cable failure" become questions about that forest.
## Cost
Time O(n + m log m), space O(n + m), one search. 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. The answer is at most
n = 200000.
## Related
Problem 1729 counts the bridges this formula adds. Problem 1736 counts the blocks, which is the vertex-removal analogue and a genuinely different number on the same graph. Problem 1737 builds the forest described above.
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 connected pieces left once every bridge has been deleted. Vertices that the deletions leave with no edges at all still count as pieces of their own, so the answer is between 1 and n. Print no other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.