What are some nice tutorial for union-find-delete data structure ?
What are some nice tutorial for union-find-delete data structure ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Persistent DSU?
i dont think it is persistent DSU, DSU with delete feature is what i need.
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.
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.
no no , its not recent one. we can delete anytime if added already.
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
yes, you are right! :)
How do you define "delete" operation?
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.
I think what you're looking for is link/cut tree, but it's very hard data structure, you can google it anyway.
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:
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.com/blog/entry/22031
Sound perfect! this is what i needed actually.