### PROBLEM LINK:

**Author:** Gerald Agapov

**Tester:** Mahbubul Hasan

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

Sqrt Decomposition, Link-Cut Tree

### PROBLEM:

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?

### EXPLANATION:

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.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.