brokie's blog

By brokie, history, 7 months ago, In English

I am working on writing a fully retroactive DSU. And after reading a paper on how to built such a data structure, I stumbled upon Link Cut Trees.

Can I make LCTs support path queries? Like minimum / maximum queries between 2 different vertices? Also, what if I need to add an edge that creates a cycle in my tree, what can I do in this case?

Any help would be greatly appreciated!

Full text and comments »

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

By brokie, history, 8 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!

Full text and comments »

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