Maintain the sum of biconnected components’ sizes squares during adding the edges in the graph.
Solution to sub tasks 1, 2, 3:
Let’s solve the following problem: you are given a graph, calculate the number of unsafe unordered pairs of vertices in it. It’s naturally the same as: calculate the number of ordered unsafe pairs of vertices and then divide it by two. Another observation is that the number of unsafe pairs equals to the number of all possible pairs minus the number of safe pairs of paths. So, we will solve this modified problem.
This time we will find the O(N+M) solution to a single query. The number of all possible pairs is naturally the sum of squares of the connected components’ sizes and the number of safe pairs is the sum of squares of the biconnected components’ sizes. Finding biconnected components is a very standard problem, generally you can obtain the new graph where connected components correspond to the biconnected components of the initial graph if you remove all the bridges from the initial graph.
So, we have solved our problem in O(M(N+M))* time. But it’s not enough to get 100 points.
Solution to all the sub tasks:
The problem can be solved in O(N log N+M) time. We will keep the idea from the previous solution, generally, we have to maintain two sums: the sum of squares of connected components’ sizes and the sum of squares of biconnected components’ sizes.
It’s very easy to maintain the first sum. We can use the DSU in order to do it in O(1) time. When the edge is added, it can change nothing or it can merge two different connected components. In the second case we just decrease the sum by squares of these two components’ sizes, merge them and then simply add the square of the size of the new connected component.
Now, how to maintain the sum of squares of biconnected components’ sizes. At first, we have already noted the fact that if we remove all the bridges, we’ll obtain biconnected components. Now, let’s note that if we shrink these biconnected components to the single vertice, and then add all the bridges again, we’ll obtain forest. There will be no cycles because the cycle would add one more BCC. Let’s have another DSU, where we will store the information about to which BCC every vertice belongs.
So, when we add an edge, there are three possible cases:
Both vertices of the edge belong to the same BCC - this edge will not change anything.
The edge connects two different connected components - connect these components (there will be an important notice about this below) and modify the first sum, as it is described above.
The edge connects two different biconnected components that belong to the same connected component - well, this is the hardest case…
Generally, in the third case, we add an edge to the tree. Obviously, it forms the cycle. And now we have to find the cycle and to shrink it to the single vertice. Naturally, it is OK to do it in O(cycle) time. Let’s say that the forest of BCCs is denoted by the ancestors’ array pr. So, we can find the LCA of these vertices simply by going up in this tree until we find some vertice that is an ancestor of the both - the first and the second vertice (let’s call them X and Y). Then we just merge all the vertices of this cycle in the BCCs’ forest and in the BCCs’ DSU and recalculate the sizes of the biconnected components.
The last important observation is that in the second case we can’t just change the value of either pr[x] or pr[y] because both x and y might be non-root vertices of their trees. So, we have to make one of these vertices a root one, because it’s obvious that only the root doesn’t have any ancestors. But which vertice should become the root of its tree? It can be proved that if we make the vertice from the smallest tree root, we will obtain amortized O(N log N) complexity. To make the vertice a root one, we just “lift” it up the tree, till the moment, when this vertice doesn’t contain any ancestor.
Summing up these facts, we finally obtain an O(N log N+M) solution to the problem that scores 100 points. The solution is an online-one, and I’ve thought of making online-type queries, but I’ve decided not to do it because, I believe, if an offline solution exists, it isn’t much easier than the provided one.
Solution to subtasks 1, 2 and 3 can be found here
Solution to all the subtasks can be found here
Can be found here