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