sherlock_holms's blog

union-find-delete DS tutorial
By sherlock_holms, history, 9 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

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

Persistent DSU?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    i dont think it is persistent DSU, DSU with delete feature is what i need.

    → Reply
»
9 years ago, # |
  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
»
9 years ago, # |
  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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    no no , its not recent one. we can delete anytime if added already.

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

      This is called the Dynamic Connectivity Problem, and it's rather complex. You can't solve it with a simple DSU structure. There are other advanced data structures you can use though, like the link-cut tree for acyclic graphs or cutset structures for general graphs.

      Full Dynamic Connectivity

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

How do you define "delete" operation?

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

    i want to delete some edge in a tree , once i remove the edge the tree will create two trees and update the parent of each tree some node of each corresponding tree.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think what you're looking for is link/cut tree, but it's very hard data structure, you can google it anyway.

      → Reply
»
9 years ago, # |
  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://codeforces.net/blog/entry/22031

→ Reply