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