Система непересекающихся множеств это структура данных (также называемая структурой данной поиска пересечения или множеством поиска слияния), которая управляет множеством элементов, разбитых на несколько непересекающихся подмножеств. Она предоставляет около-константное время выполнения операций (ограниченное обратной функцией Акерманна) по добавлению новых множеств, слиянию существующих множеств и опеределению, относятся ли элементы к одному и тому же множеству.
Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.
Основные операции:
- MakeSet(x) - создаёт одноэлементное множество {x},
- Find(x) - возвращает идентификатор множества, содержащего элемент x,
- Union(x,y) - объединение множеств, содержащих x и y.
После некоторых операций объединения, некоторые множества собраны вместе