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