Pancake's blog

Graph problem
By Pancake, 12 years ago, In English

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!

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

You can start from end and add edges to the graph.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

It's exactly this problem: http://acm.timus.ru/problem.aspx?space=1&num=1671

Solution is in Rev. 1.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply