no_oneplb's blog

Query regarding Union-Find ?
By no_oneplb, history, 18 months ago, In English

Hello Codeforces,

I have a graph question where both edge addition and deletion are allowed as queries.After each query, you need to maintain the component each vertex is a part of.The addition query is straight-forward merge but i don't know how to implement edge deletion query.

Can anyone explain or provide any link to an article which address this problem?

Basically, i'm looking for this- Problem

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by no_oneplb (previous revision, new revision, compare).

→ Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

If all the additions/deletions are known ahead of time (offline processing), then you can use this technique: https://cp-algorithms.com/data_structures/deleting_in_log_n.html

→ Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

If you have a offline queries for deletion and addition you could just store them and then arrange in such a order that difference would be evident. Keep in mind that you do not need to store the whole state of the parent array, but you do need to stop using path compression for this since you will need to store and remember from where you merged the set of vertices you're now disassociating by deleting the current edge.

I have no clue how one would go about doing this for online queries but i can only imagine it would require some grand DS that i have no clue about lol.

Anyways, good luck :)

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you can easily maintain a deletion query if deleting the last edge for each deletion query works for you , basically use a stack

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Note: To access following links you need to register for the ITMO course here. This problem can be found here. There is an explanation on how to solve (a very similar problem) here.

→ Reply