FIND-SET with path compression (two-pass recursion)

Answer

FIND-SET(x): if x != x.p: x.p = FIND-SET(x.p) # compress: point straight at root return x.p

The recursion ascends to the root; as it unwinds, x.p = FIND-SET(x.p) repoints every node on the path directly to the root. Future finds on those nodes are O(1).