Pidu's blog

Split operation in disjoint set
By Pidu, 14 years ago, In English

Does disjoint set support split operation? Suppose there are 3 edges 1-2,2-3,3-4, all nodes {1,2,3,4} are in same set. If 2-3 edge is removed that it is split into 2 sets {1,2} and {3,4}. How can i perform such operations? If its impossible using disjoint set, please suggest a good data structure.

Any help is greatly appreciated. Thanks.

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

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

As far as I know, disjoint set structure doesn't support split operation.

→ Reply
»
14 years ago, hide # |
← Rev. 3  
Vote: I like it +11 Vote: I do not like it

If you're working with intervals (the so called "Interval union-split-find problem"), you can use any data structure that supports fast insertions and deletions. For example, STL's set should work fine. The lower bound is actually reached using van Emde Boas trees, which support every operation in time. This works because every union operation corresponds to a deletion, while every split is an insertion.

There are some other special cases other than the interval one (cyclic, ordered, ...). See this [1] for a complete reference (it also shows some recent result for the general union-split-find problem)

If by "split" you mean the possibility to backtrack, than there are some interesting results by Mannila and Ukkonen [2] (partial backtracking) and Apostolico, Italiano, Gambosi and Talamo [3].

[1] Katherine Jane Lai, Complexity of Union-Split-Find Problems

[2] Mannila, H. and Ukkonen, E., The set union problem with backtracking, Proceedings of the 13th Inter- national Colloquium on Automata, Languages and Programming (ICALP 86), LNCS, 226, Springer- Verlag, Berlin, 236–243, 1986.

[3] Apostolico, A., Italiano, G.F., Gambosi, G., and Talamo, M., The set union problem with unlimited backtracking, SIAM J. Comput., 23, 50–70, 1994.

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

Problem about connectivity components in graph with requests to add and delete adges is calles "Dinamic Connectivity problem". It's known and hard. I think some inforation can be fund in internet. There are quite complicated online solutions with amortized time O(log2n), and more easy offline solutions with times . I heard about solutions with good not-amortized time, but i don't know anything about them. Also, i don't know if there are better solutions, than i mentioned. Google will help you.

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

    About half a year ago I asked niyaznigmatul about a fast dynamic connectivity algorithm, he explained me the algorithm that works in O(log2n) per query. He also told me that this algo can be improved to work in O(log n) per query, but he explained it very briefly. I've thought a lot about his explanations, and now I've understood his improvement. Maybe, later I'll write an article about it.

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

An offline version can be achieved in O(sqrt(q)) time using SQRT decomposition technique.

There is a nice article about it, but it is in Russian.

→ Reply