117
правок
Изменения
→С помощью списка
=== С помощью списка ===
'''Оценка работы:'''
{| border="1"
|<tex>init</tex>
|<tex>O(1)</tex>
|}
Пусть каждое множество хранится в виде списка. Вначале создается <tex>n </tex> списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на следующий элемент<tex>(next) </tex> и ссылку на хвостголову (tail<tex>head</tex>). Тогда для объединения множеств надо будет просто перекинуть ссылку <tex>next </tex> на начало другого множества. Таким образом, <tex> union </tex> работает за <tex> O(1) </tex>.
Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам <tex>next'ам</tex>, пока он не указывает на Null <tex>null</tex> {{ - -- }} тогда мы нашли элемент-представитель. Таким образом, <tex> find </tex> работает за <tex> O(n) </tex>.
Псевдокод:
for i = 0 to n - 1:
s[i].set = i
s[i].next = Nullnull s[i].tail head = s[i]
find(x): //подразумевается, что x - ссылка на один из элементов
x.next = y.head //соединили списки
y.head = x.head //сделали корректную ссылку на голову для представителя нового списка
'''Пример работы:'''
Два списка до операции <tex>union</tex>:
