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 per operation (no path compression means trees stay balanced by rank).