Bridges: The Final Battle

Does your thesis have practical applications?

_____________________________________________________

Popular question

Legend

Sergey is nearing the completion of his thesis. Since December, the topic has remained unchanged: "Dynamic 2-Edge-Connectivity Problem." An algorithm has been developed, tested, and its O(K \log K) complexity has been proven. Now, only the chapter on practical applications remains to be written.

But what practical use could there be for the Dynamic 2-Edge-Connectivity Problem? It's a challenging question—perhaps even harder than the problem itself. However, the thesis must be defended, so an answer is urgently needed.

Thus, here's a practical application: you can make a contest problem based on this topic!

Problem

You are given an undirected graph with up to 10^5 vertices. Initially, the graph contains no edges. You will process queries of the form ADD $x$ $y$ and DEL $x$ $y$—adding or removing the edge between vertices $x$ and $y$.

At any moment, you must determine how many bridges there are in the current graph.

There are never multiple edges or loops in the graph at any time.

If a "delete an edge" command is issued, the corresponding edge is guaranteed to exist in the graph at that moment.

Hints

A thesis is called a "thesis" precisely because it cannot be written in just $5$ hours. So here are $5$ hints:

1. Add and remove edges—make an edge "alive" for a certain time interval.

2. Use the "Divide and Conquer" approach.

3. Compress biconnected components.

4. Even after compressing biconnected components, if the number of queries is small, the graph can still be further reduced.

5. An O(K \log K) solution exists.