Sqrt Decomposition, Link-Cut Tree
Given an undirected graph, with N nodes and M edges, answer Q queries – how many connected components are there, if we only admit the l-th edge to r-th edge?
I know two solutions for this problem. The first one is Link-Cut Tree related, using O((Q + M)logN) time. The second one solves the problem via Sqrt Decomposition, using O((Q + M)sqrt(M)) time.
Both solutions are offline solutions. That is, we first load all queries, and then deal them in some order we defined.
Link-Cut Tree solution
Sort the queries ascending by their right ends. Use a Link-Cut Tree maintaining the maximum spanning tree (forest, if edges are not enough) using the edges from 1-st to r-th (the weight of a edge is its sequential number. The 1-st edge is weighted 1, 2-nd is 2, …). This can be done because we can use the Link-Cut Tree to find the minimum edge between two tree-node, then delete it and insert the new edge in O(logN) time.
For a query of [l, r], count the number of edges with weight larger than or equal to l, denoting it as C. This can be done by some other data structures, like Segment Tree or Fenwick Tree. Also, it requires O(logN) time for each update of edges in the maximum spanning tree. Then, the answer of the query, is N - C.
The correctness of this algorithm can be proven by the Kruskal algorithm. First, greedily apply it to the edges from r-th to l-th (in the described order) and get a spanning tree. It should be a part of the spanning tree got by greedily applying it to the edges from r-th to 1-th.
Sqrt Decomposition solution
Similar to Codeforces 86D, which is the first problem I saw this method using as an offline algorithm, this problem can be solved by the Sqrt Decomposition.
If you can solve that problem, then, the idea here is quite simple:
- divide 1…M edges into sqrt(M) blocks, each has sqrt(M) edges.
- group the queries by the block IDs of their left ends.
- for all queries in the same group (begin at the same block), sort them ascending by their right ends.
Now, we are considering the queries begin at the same block:
- scan the queries one by one and use a union-find set to maintain the connectivity of subgraph consisting of edges from the first edge of the next block to the last edges of the current query.
- For the edges between the left end of the current query and the last edge of the beginning block (at most sqrt(N) edges here, because they are in the same block), run some brute-force union operations to merge them to get the answer.
- After the brute-force merge, we need to restore the union-find set we maintained before. Because there are at most sqrt(N) merge operations, we can record the places we changed (at most sqrt(N), too) and restore them.
Therefore, we can solve this problem in O((Q + M)sqrt(M)) time using this idea.