Greetings folks, I've been struggling with the following problem:
I don't have a clear definition of the task but in most cases, it looks something like that:
You are given a squared plane (that is every vertex has integer coordinates $$$1 \le x_i, y_i \le N$$$) with some vertices disabled, edges between vertices can only go in 8 directions (chess king moves), and are always present if the vertices are present.
The task is to answer $$$Q$$$ queries, where a query asks you to remove a small number of $$$X$$$ vertices from the graph, recalculate articulation points (cutpoints) and bridges and add them back.
The constraints are something like this:
$$$1 \le Q \le 8 \cdot 10^{5}$$$ — the amount of queries
$$$4 \le X \le 40$$$ — the amount of deleted points in the query
$$$1 \le N \le 200$$$ — borders of the bounding box of the graph (number of vertices can go up to $$$N^2$$$)
I've always been struggling with biconnected components, so I'm unsure how to solve this. I've seen the algorithm that keeps DSU with biconnected components, but it was hard to comprehend and I'm not sure whether it is applicable to cutpoints.
Queries are not online, thus I felt like something like dynamic-connectivity offline which consists of rollbacking DSU would work, but I'm not really sure how exactly to apply this
Currently, my solution is $$$O(Q \cdot V \log E)$$$ which takes too long to compute without getting new hardware. That is bruteforce bridges (dfs) with set to keep track of them, probably $$$\log E$$$ is somewhat easy to remove, but it doesn't seem to help in the big picture, it feels like this problem has a better solution
The source is neither a competitive programming task nor an interview question.
Any help appreciated
