Hi everyone, I get stuck with this problem.
Give an undirected graph with n (n <= 2.10^3) vertices and m (m <= 3.10^4) edges. There are q (q <= 10^4) queries.
You have to answer each query L, R : How many connected components if we remove edges from index L to index R
The first line contains 2 integer numbers n and m.
Next m lines contain the edges of this graph, each line contains 2 integer number u and v representing one edge.
The next line contains a single integer q : the number of queries
Next q lines contain 2 integer L and R
Example
Input:
6 5
1 2
5 4
2 3
3 1
3 6
6
1 3
2 5
1 5
5 5
2 4
3 3
Output
4
5
6
3
4
2
Thank!
Looks like variation of dcp offline
Is there an easier way to solve this without lcp?
I think he does not mean the LCP array (of course this is a graph problem, he wouldn't mean a string algorithm), instead he means the Dynamic Connectivity Problem, otherwise abbreviated as DCP
Let's say that $$$i$$$-th edge is $$$leftBad$$$ if graphs consisting of $$$i-1$$$ and $$$i$$$ first edges are the same in terms of connectivity, which means that if you used DSU on first $$$i-1$$$ edges, using DSU on $$$i$$$-th edge wont invoke any Union. In the same way we can define $$$rightBad$$$ edges, we will just look at suffix of edges instead of prefix. Let's say that $$$i$$$-th edge is $$$leftGood$$$ if it's not $$$leftBad$$$. Of course there are at most $$$n-1$$$ edges that are $$$leftGood$$$ (the same for $$$rightGood$$$).
We can see, that we only need to use edges that are $$$leftGood$$$ on some prefix and edges that are $$$rightGood$$$ on some suffix. This way in every query we can iterate over these edges and use DSU on them, algorithm will be slightly faster than just iterating over all the edges for every query. Complexity is $$$O(n \cdot q \cdot \log^*n)$$$ instead of $$$O(m \cdot q \cdot \log^*n)$$$.
But there is faster solution. We already know that we only need to use some edges, so we can iterate over every possible combination of these edges, for example we'll use first $$$x$$$ $$$leftGood$$$ edges and last $$$y$$$ $$$rightGood$$$ edges. We can see that it's easy to go from state $$$(x,y)$$$ to state $$$(x,y+1)$$$, it's just using one Union. It's basically two pointers technique. If we are in some state we can answer all the queries which use exactly this set of $$$goodLeft$$$ and $$$goodRight$$$ edges. It's easy to do if we sort queries. Now the complexity if $$$O(n^2 \cdot \log^*n + q \cdot \log q)$$$.
I know that this solutions may not be clear from my comment, so please, let me know if you need more detailed explanation!
Oh thanks, I got it.
Sorry for the late reply.