117
правок
Изменения
Нет описания правки
* union(x, y) {{ --- }} объединяет множества, содержащие x и y
* find(x) {{ --- }} возвращает представителя множества, в котором находится x
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов x и y одному множеству достаточно сравнить find(x) и find(y).
[[Файл:DSU_1_Example.png|500px|left|thumb|Пример работы СНМ]]
<br clear="all" />
== Реализации ==
=== С помощью массива ===
|<tex>O(1)</tex>
|}
Будем хранить множество в виде списка. Вначале создается n списков, в которых каждый элемент является представителем своего множества. Для каждого элемента списка будем хранить ссылку на следующий элемент (next) и ссылку на голову (head). Причем ссылка на head будет корректна только у элемента-представителя. Тогда для объединения множеств достаточно надо будет просто перекинуть ссылку next у представителя одного множества на начало другого множества и скорректировать head у представителя другого множества. Таким образом, <tex> union </tex> работает за <tex>O(1)</tex>.
Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам next, пока он не указывает на null {{ --- }} тогда мы нашли элемент-представитель. Таким образом, find работает за <tex>O(n)</tex>.
