4

I am looking for a data structure that can support union, find, and de-union fairly efficiently (everything at least O(log n) or better) as a standard disjoint set structure doesn't support de-unioning. As a background, I am writing a Go AI with MCTS [http://en.wikipedia.org/wiki/Monte_Carlo_tree_search], and this would be used in keeping track of groups of stones as they connect and are disconnected during backtracking. I think this might make it easier as de-union is not on some arbitrary object in the set, but is always an "undo" of the latest union.

I have read through the following paper and, while I could do the proposed data structure, it seems a bit over kill and would take a while to implement http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1773&context=cstech

While O( a(n)) would be great, of course, I'm pretty sure path compression won't work with de-union, and I'd be happy with O(log n). My gut tells me a solution might be heap related, but I haven't been able to figure anything out.

user1040423
  • 143
  • 8

2 Answers2

9

What you're describing is sometimes called the union-find-split problem, but most modern data structures for it (or at least, the ones that I know of) usually view this problem differently. Think about every element as being a node in a forest. You then want to be able to maintain the forest under the operations

  • link(x, y), which adds the edge (x, y),
  • find(x), which returns a representative node for the tree containing x, and
  • cut(x, y), which cuts the edge from x to y.

These data structures are often called dynamic trees or link-cut trees. To the best of my knowledge, there are no efficient data structures that match the implementation simplicity of the standard union-find data structure. Two data structures that might be helpful for your case are the link/cut tree (also called the Sleator-Tarjan tree or ST-tree) and the Euler-tour tree (also called the ET-tree), both of which can perform all of the above operations in time O(log n) each.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

The other answer is over-complicated. You can use a standard union-find data-structure where every time you set parent[x] = y, you append (x, old_parent) to a stack. On backtracking, you just reset to the old value.

You can do the same thing with path compression, but the overhead may not pay off. Also, if you make multiple modifications per union call, you need to add separators to the stack so you know when to stop.

user1502040
  • 451
  • 3
  • 13