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
Also, if there is a good heuristic that would tell whether "a graph could have articulation points" — that would help in my specific case since I know for certain that queries are more or less random, so the odds are that graph does not have nor bridges nor articulation points
It might be helpful to take a look at the Dynamic Connectivity Set to get some ideas for tools you can use. If you are only adding edges, or if your remove queries are predictable, then you can use a link cut tree, like in this submission to find bridges.
There is also some nice discussion about bridge identification here, but it doesn't help with articulation points unfortunately.
Is this some sort of homework? xd
The graph in question is a planar graph. There are some magical observations to solve this. I have a solution that is somewhat $$$O(8*X*logN^2)$$$ per query but not sure if good enough for you or is there something better :)
First, let's answer a simpler question. How to determine if a node/edge is critical? When considering a planar graph, it helps to consider their dual graph. A dual graph of a planar graph is such that each dual node corresponds to a plane, and each dual edge corresponds to one edge on the original graph.
Let's start from the original graph. Every dual nodes are present, dual edges are present iff its corresponding edge on the original graph is NOT present. An edge $$$(u, v)$$$ (with its dual $$$(u', v')$$$) is critical iff $$$u'$$$ and $$$v'$$$ are on the same dual connected component. A node $$$u$$$ is critical iff its degree is strictly greater than the number of different connected components formed by its 8 surrounding dual nodes.
Thus queries of "removing nodes/edges on graph" becomes "adding edges on dual". And it is easy to track connected components on the dual graph with a DSU (with rollback for answering queries).
How to count critical nodes/edges now? If the queries are of remove type, then only non-criticals become criticals, and not vice-versa. I haven't worked out the details of how to exactly solve this, but it should be something along the lines of tracking dual connected components with a DSU, and counting edges/nodes involving the merged dual components for each query.
Nah, it isn't homework, just a hobby
Could you elaborate on this? I don't seem to understand why this is the case.
Dual graph seems very promising, any query processing in $$$\Omega(N^2)$$$ is going to be significantly better than my current solution
I made a small mistake :) It's not actually planar, I got too accustomed to triangular lattices that I forgot each square has two crosses. But you can still probably fix it by, say, putting a node in the center of each cell, or consider duality between king's move and rook's move.
Anyway I found some maybe useful readings for the planar case. Text to link
(I made a little edit below from the original comment, sorry) :)
Let's show that degree $$$\ge$$$ number of dual CCs. This is easy. Suppose degree is $$$D$$$, then these $$$D$$$ edges can only separate the surface surrounding the vertices into at most $$$D$$$ different planes. Now suppose degree $$$>$$$ dual CCs. This means there is at least one set of edges that is adjacent to two dual nodes of the same CC. It follows that said set of edges are critical (when all removed), and thus this node, adjacent to the critical edges, is also critical (unless it has degree $$$1$$$ to begin with).