Идея

В процессе find(x) мы не просто находим представителя, но и после этого подвешиваем все пройденные вершины к нему. Эта процедура называется two-pass method: мы делаем сразу 2 действия (найти родителя, возвращаемся назад (т.е. рекурсии заканчиваются) и подвешиваем к корню текущие вершины)

Улучшенный find(x) - $\approx O(1)$, см пояснение на странице ранее

int find(x) {
	if (arr[x] == x) {
		return x; 
	} 
	
	arr[x] = find(arr[x]); // подвешиваем текущий к представителю, которого найдём рекурсивно
	return arr[x]; 
}