sherlock_holms's blog

union-find-delete DS tutorial
By sherlock_holms, history, 10 years ago, In English

What are some nice tutorial for union-find-delete data structure ?

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

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Persistent DSU?

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

it's easy to implement delete operation for trivial DSU. Just mark element as deleted and increase counter by one. Once counter will be equal to, say, half of DSU size, rebuild the whole data structure and set counter to 0.

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

If you only want to delete the most recent edge, you can store a stack and reverse the union (that is, store each element's previous parents and size/rank and restore them) by popping off the last stack element.

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

How do you define "delete" operation?

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

I don't think there is an easy way of doing this. You can rebuild the DSU after each delete, but I don't think this is what you need.

But you can solve this offline. For that just create a segment tree on the queries and every delete/add edge will be something like that:

ADD 1 2    (let this be index "i")
....... 
DEL 1 2    (let this be index "j")
.......
ADD 1 2    (let this be index "i1")
....... 
DEL 1 2    (let this be index "j1")
.......

Then edge from 1 to 2 is available in time [i; j] and [i1; j1]. So you can construct a segment tree in witch every node stores what edges are available in it. After that with a persistent DSU + a dfs in the segment tree the problem can be solved in O(n*log^2(n)).

PS: This will be a solution if you have 3 types of queries: ADD, REMOVE edge and ASK if vertexes U and V are connected.
PS2: I actually was solving the same problem some time ago: http://mirror.codeforces.com/blog/entry/22031

→ Reply