Recently, at the MIPT: The Fall training camp on the contest from Alexander Milanin was a problem from Petr Mitrichev Contest 7. We were given a graph and a set of queries like "suppose we removed from the graph k ≤ 4 edges. Check whether graph is still connected?" I want to talk further about the solution of a more general problem, when the edges are added and removed without additional constraints in offline. The first algorithm with such an assessment was offered by David Eppstein in 1992, reducing it to fully dynamic minimum spanning tree problem, but here we will focus on a simple algorithm, proposed in 2012 by Sergei Burunduk1 Kopeliovich.
Let's assume that there are three types of queries & mdash; add the edge (
+), remove the edge (
-) and find out some information about the graph (
?) (in this case, let it be the number of connected components of the graph). We assume that we received a k queries. Consider the k + 1 points of time & mdash; initial and k points after each query. For convenience, we transform the requests of the first kind in the queries of the form " i-th edge is present in the column from the time l to the time r" (
Thus, suppose we have a graph G = < V, E > and the set of queries. Let be a set of edges, which are always present in it (that were originally there and were no requests for their removal). Let's compress each connected component formed from such edges in one vertex and construct a new graph of these vertices. Also delete all vertices that are not mentioned in the list of requests (to work with the graph of k vertices). Remade queries so that if in the initial graph query was assigned to a pair of vertices (a, b), now it will be assigned to a pair of vertices (comp(a), comp(b)). We see that the execution of
? requests in new graph will have exactly the same result as in the initial. It is further proposed an algorithm: divide the time interval which is currently being processed in two halves and recursively solve firstly the left and then the right side, and thus obtain answers for the entire set of queries. Base & mdash; a single point of time, answered trivially & mdash; at this point we fed to the input graph without edges, therefore, for any query answer will be the number of vertices in the graph. At each step, the query processing subsegment [l;r), we will keep only those vertices that are mentioned on this subsegments, then the request [l;r) will be processed in the O(r - l), which will be in the sum over all subsegments.
Sergei also proposed a similar idea of algorithm for a biconnected components (and bridges) in a dynamically changing graph in offline. You can read about it in his diploma, which is attached below.
To summarize, I would like to offer traditionally solve several problems on the topic. Especially for this was made training. Good Luck & Have Fun!