The Full DSU Template

Here is the complete DSU implementation you will use in hundreds of problems.

The parent array tracks who each element reports to. The size array tracks how big each group is. Initially, everyone is their own leader with size $1$.

The find function follows parent pointers until it reaches a root (where parent[x] = x). Path compression flattens the tree by making every visited node point directly to the root. This is what makes DSU blazingly fast.

The union function merges two groups. It finds both roots, then attaches the smaller tree under the larger one. Union by size keeps trees shallow, preventing worst-case linear chains.

Together, path compression and union by size give amortized $O(\alpha(n))$ per operation, where $\alpha$ is the inverse Ackermann function. For all practical purposes, this is constant time.

parent := array of size n
size := array of size n

function init(n)
    for i from 0 to n-1
        parent[i] := i
        size[i] := 1

function find(x)
    if parent[x] != x then
        parent[x] := find(parent[x])
        return parent[x]

function union(x, y)
    rootX := find(x)
    rootY := find(y)
    if rootX = rootY then return false
    if size[rootX] < size[rootY] then
        swap(rootX, rootY)
        parent[rootY] := rootX
        size[rootX] := size[rootX] + size[rootY]
        return true