Hello I have been trying to come up with an idea for the following graph theory problem :
Given an undirected graph of N vertices and E edges , You have to process a list of Q queries. In query q (1 <= q <= Q) , you remove some edge e , and you are to report the number of components in the new graph. Removal of each edge is permanent , i.e for query #q you should assume that ALL the given q edges have been removed.
N , E and Q can be at most 200,000 Thanks a lot!
You can start from end and add edges to the graph.
It's exactly this problem: http://acm.timus.ru/problem.aspx?space=1&num=1671
Solution is in Rev. 1.
Thanks a lot ! I learnt the concept of disjoint sets and got accepted. Is anyone aware of some problems in which you need to use both "union by rank" and "path compression" to get AC ?