Union-Find uses a parent array. If parent[i] == i, then is a root. Otherwise, parent[i] points to '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.