Union-Find with Rollback

Standard Union-Find doesn't support "undo." For problems needing rollback, maintain a history stack:

class RollbackUnionFind:
    function init(n):
        this.parent = array of [0, 1, ..., n-1]
        this.rank = array of n zeros
        this.history = [] // (node, old_parent, old_rank)

    function union(x, y):
        rootX = this.find(x)
        rootY = this.find(y)
        if rootX == rootY:
            return false
        // Store state before union
        this.history.add((rootX, this.parent[rootX], this.rank[rootX]))
        this.history.add((rootY, this.parent[rootY], this.rank[rootY]))
        // Perform union
        ...

    function rollback():
        (node, parent, rank) = this.history.pop()
        this.parent[node] = parent
        this.rank[node] = rank

Important: rollback Union-Find cannot use path compression (it makes history tracking complex). You get $O(\log n)$ operations.