Пусть индекс - элемент, значение - индекс его родителя в массиве. У корня родитель - сам корень.
Операции Disjoint-set forests без эвристики
Эвристика сжатия путей (path compression)
Время работы как find(x), так и unoin(x, y) на лесе размера N есть O(α(N)). Под α(N) в математике обозначается обратная функция Аккермана, то есть, функция, обратная для f(N) = A(N, N). Функция Аккермана A(N, M) известна тем, что у нее колоссальная скорость роста. К примеру, A(4, 4) = $2^{2^{2^{65536}}} - 3$, это число поистине огромно. Вообще, для всех мыслимых практических значений N обратная функция Аккермана от него не превысит 5. Поэтому её можно принять за константу и считать O(α(N)) $\approx$ O(1). Источник: https://habr.com/ru/articles/104772/