# Система непересекающихся множеств

**Система непересекающихся множеств** это структура данных (также называемая структурой данной поиска пересечения или
множеством поиска слияния), которая управляет множеством элементов, разбитых на несколько непересекающихся подмножеств.
Она предоставляет около-константное время выполнения операций (ограниченное обратной функцией Акерманна) по *добавлению
новых множеств*, *слиянию существующих множеств* и *опеределению, относятся ли элементы к одному и тому же множеству*.

Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура
данных для эффективной реализации.

Основные операции:

- *MakeSet(x)* - создаёт одноэлементное множество {x},
- *Find(x)* - возвращает идентификатор множества, содержащего элемент x,
- *Union(x,y)* - объединение множеств, содержащих x и y.

После некоторых операций *объединения*, некоторые множества собраны вместе

## Ссылки
- [СНМ на Wikipedia](https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2)
- [СНМ на YouTube](https://www.youtube.com/watch?v=bXBHYqNeBLo)
