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

---

Система непересекающихся множеств (англ. disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: ${\displaystyle \{\mathrm {Union} ,\mathrm {Find} ,\mathrm {MakeSet} \}}$.

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

Пусть ${\displaystyle S}$ конечное множество, разбитое на непересекающиеся подмножества (классы) ${\displaystyle X_{i}}$:

Каждому подмножеству ${\displaystyle X_{i}}$ назначается представитель ${\displaystyle r_{i}\in X_{i}}$. Соответствующая система непересекающихся множеств поддерживает следующие операции:

Тривиальная реализация сохраняет принадлежность элементов из ${\displaystyle S}$ и представителей ${\displaystyle r_{i}}$ в индексном массиве. На практике же чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Find. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

Для ускорения операций Union и Find могут быть использованы эвристики Union-By-Size, Union-By-Height, Random-Union и сжатие путей.

---