makeSet(x) - $O(1)$

void makeSet(x) {
	arr[x] = x; 
}

find(x) - $O(n)$

int find(x) {
	while (arr[x] != x) {
		x = arr[x]; 
	}
	
	return x; 
}

<aside> ℹ️ Кроме того, будем называть путь, который прошёл find(x) как find path.

</aside>

union(x, y) - $O(n)$

void union(x, y) {
	xRoot = find(x); 
	yRoot = find(y); 
	
	// подвешиваем дерево yRoot к xRoot
	arr[yRoot] = xRoot; 
}