Изменения

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head</tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head</tex>. Значит <math> \mathrm{find } </math> работает за <tex> O(1) </tex>.

Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head</tex>. Таким образом, <math> \mathrm{union } </math> работает за <tex> O(n) </tex>.Чтобы объединить два списка, нужно хранить ссылку на <tex> tail</tex>. Ее можно хранить в голове списка.

<code> '''int''' s[n] '''func''' init(): '''for ''' i = 0 '''to ''' n - 1:

</code> <code> '''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов</font> '''return ''' x.head.data </code> <code> '''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>

'''if ''' x == y: '''return''' <font color=green> // соединим списки</font>

<font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font>

<font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества "<tex> y"</tex> </font> '''while ''' y != <tex> \neq </tex> null: