Basic Structure

Union-Find uses a parent array. If parent[i] == i, then $i$ is a root. Otherwise, parent[i] points to $i$'s parent.

class UnionFind:
    function init(n):
        this.parent = array of [0, 1, ..., n-1]  // each node is its own parent

Initially, every node is its own root (a forest of single-node trees).

To find the root of a node, follow parent pointers:

function find(x):
    while this.parent[x] != x:
        x = this.parent[x]
    return x

To check if two nodes are connected:

function connected(x, y):
    return this.find(x) == this.find(y)

Same root means same component.