Union by Size

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 $O(\log n)$ tree height without path compression, and $O(\alpha(n))$ with path compression.