Persistent Union-Find

Standard Union-Find is destructive: find changes the structure (path compression).

For persistence, use Union-Find without path compression:

class PersistentUF:
    // Persistent array of parents
    parent: PersistentArray
    rank: PersistentArray
    version: int

    function find(v, node)
        while parent.get(v, node) != node
            node := parent.get(v, node)
        return node

    function union(v, a, b)
        rootA := find(v, a)
        rootB := find(v, b)
        if rootA = rootB then
            return v // same version

        // Union by rank (no path compression)
        rankA := rank.get(v, rootA)
        rankB := rank.get(v, rootB)
        newVersion := v + 1

        if rankA < rankB then
            parent.set(v, rootA, rootB)
        else if rankA > rankB then
            parent.set(v, rootB, rootA)
        else
            parent.set(v, rootB, rootA)
            rank.set(v, rootA, rankA + 1)

        return newVersion

Find is $O(\log n)$ per operation (no path compression means trees stay balanced by rank).