117
правок
Изменения
→С помощью списка
|<tex>O(1)</tex>
|}
Будем хранить множество в виде списка. Вначале создается n списков, в котором которых каждый элемент является представителем своего множества. Для каждого элемента списка будем хранить ссылку на следующий элемент (next) и ссылку на голову (head). Причем ссылка на head будет корректна только у элемента-представителя. Тогда для объединения множеств надо достаточно будет просто перекинуть ссылку next на начало другого множестваи скорректировать head. Таким образом, union работает за <tex>O(1)</tex>.
Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам next, пока он не указывает на null {{ --- }} тогда мы нашли элемент-представитель. Таким образом, find работает за <tex>O(n)</tex>.
