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

Структура данных для непересекающихся множеств поддерживает набор $S=\{S_{1},S_{2},\ldots ,S_{k}\}$ непересекающихся динамических множеств. Каждое множество идентифицируется представителем, которые представляет собой некоторый элемент множества. В ряде приложений не имеет значения какой элемент множества используется в качестве представителя; главное, чтобы при запросе представителя множества дважды, без внесения изменений в множество между запросами, возвращался один и тот же элемент.

Структура данных для непересекающихся множеств требует поддержку следующих операций:

MAKE_SET(x) создает новое множество, состоящее из одного элемента (который соответственно становится его представителем) x. Поскольку множества непересекающиеся, требуется, чтобы х не входил ни в какой иное множество.

UNION(x, y) объединяет динамические множества, которые содержат x и y (обозначим $S_{x}$ и $S_{y}$), в новое множество. Полагается что до выполнения операции указанные множества не пересекались. Представителем образованного в результате множества является произвольный элемент $S_{x}\cup S_{y}$. Поскольку необходимо, чтобы множества были непересекающимися, операция UNION должна уничтожать множества $S_{x}$ и $S_{y}$.

FIND_SET(x) возвращает указатель на представителя множества, в котором содержится элемент x.

Примеры конкретных структур данных для непересекающихся множеств

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

Литература

• Томас Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

Ссылки

• Визуализатор работы некоторых структур данных для непересекающихся множеств
• Реализация непересекающихся множеств в коллекции библиотек C++ Boost