Union by size attaches the smaller tree under the larger tree:
class UnionFind:
function init(n):
this.parent = array of [0, 1, ..., n-1]
this.size = array of n ones
function union(x, y):
rootX = this.find(x)
rootY = this.find(y)
if rootX == rootY:
return
if this.size[rootX] < this.size[rootY]:
this.parent[rootX] = rootY
this.size[rootY] += this.size[rootX]
else:
this.parent[rootY] = rootX
this.size[rootX] += this.size[rootY]
Size is often more useful than rank because it tells you the actual component size. This is useful for problems that ask "how many nodes in this component?"
Both rank and size achieve tree height without path compression, and with path compression.