brokie's blog

Fully Retroactive DSU
By brokie, history, 5 months ago, In English

Hello everyone! I am trying to solve the following problem:

You are given a DSU (Union Find) data structure, and you need to do the following queries efficiently:

  • Go back to time t, and insert a union operation (Union(u, v, t)) at time t.
  • Undo the union at time t.
  • Given time t, and two nodes u, v check if nodes u and v are in the same connected component at that time.

Any help or offline / online solution would be perfect!

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

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

Undoing operations online is quite hard. This is a solution to the online problem without undoing operations: Maintaing mst with onl8ne edge insertions You can use offline deletion trick on the above DS for your general problem. Hope it is still relevent

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

use a stack its called rollback dsu

this is oonline solution btw

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

DSU with rollbacks + splitting queries into blocks would work in some sqrt time complexity. You can see APIO 2019 Bridges for some similar solution.

→ Reply