The Set Union Problem with Unlimited Backtracking
Alberto Apostolico, Giuseppe Francesco Italiano, Giorgio Gambosi, Maurizio Talamo · SIAM Journal on Computing · 1994
An extension of the disjoint set union problem is considered, where the extra primitive backtrack $(i)$ can undo the last i unions not yet undone. Let n be the total number of elements in all the sets. A data structure is presented that supports each union and find in $O({{\log n} / {\log \log n}})$ worst-case time and each backtrack$(i)$ in $O(1)$ worst-case time, irrespective of i. The total space required by the data structure is $O(n)$. A byproduct of this construction is a partially persistent data structure for the standard set union problem, capable of supporting union, find, and find-in-the-past operations, each in $O({{\log n} / {\log \log n}})$ worst-case time. All these upper bounds are tight for the class of separable-pointer algorithms as well as in the cell probe model of computation.