|<tex>O(1)</tex>
|}-->
====Новая версия====
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на head, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на head. Значит find работает за <tex> O(1) </tex>.
Чтобы объединить два списка, нужно хранить ссылку на tail. Ее можно хранить в голове списка.
'''Псевдокод:'''
s[n]
init():
[[Файл:DSU_list_example.png|800px|left|thumb|Пример работы union]]
<br clear="all"/>
====Старая версия====
Будем хранить множество в виде списка. Вначале создается n списков, в которых каждый элемент является представителем своего множества. Для каждого элемента списка будем хранить ссылку на следующий элемент (next) и ссылку на голову (head). Тогда для объединения множеств надо будет перекинуть ссылку next у представителя на начало другого множества. Таким образом, union работает за <tex> O(1) </tex>.
Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам next, пока он не указывает на null {{ --- }} тогда мы нашли элемент-представитель. Таким образом, find работает за <tex>O(n)</tex>.
'''Псевдокод:'''
s[n]
init():
for i = 0 to n - 1:
s[i].set = i
s[i].next = null
s[i].head = s[i]
find(x): // подразумевается, что x {{ --- }} ссылка на один из элементов
while x.next != null:
x = x.next
return x.set
union(x, y): // здесь важно, что x и y {{ --- }} представители множеств
if x == y:
return
else:
x.next = y.head // соединили списки
y.head = x.head // сделали корректную ссылку на голову для представителя нового списка
'''Пример работы:'''
Два списка до операции union:
[[Файл:DSU_1_X.png]]
[[Файл:DSU_1_Y.png]]
Два списка после операции union:
[[Файл:DSU_1_XY.png]]
== Другие реализации ==
