Блог пользователя sherlock_holms

union-find-delete DS tutorial
Автор sherlock_holms, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Persistent DSU?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you define "delete" operation?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.me/blog/entry/22031

→ Ответить