Матеріал з Ціклопедіі
Структура даних для непересічних множин підтримує набір [math] S = \ [/ math] непересічних динамічних множин. Кожне безліч ідентифікується представником. які є певний елемент множини. У ряді програм не має значення який елемент безлічі використовується в якості представника; головне, щоб при запиті представника безлічі двічі, без внесення змін до безліч між запитами, повертався один і той же елемент.
Структура даних для непересічних множин вимагає підтримку наступних операцій:
MAKE_SET (x) створює нове безліч, що складається з одного елемента (який відповідно стає його представником) x. Оскільки безлічі непересічні, потрібно, щоб х не входив ні в який інший безліч.
UNION (x, y) об'єднує динамічні множини, які містять x і y (позначимо [math] S_x [/ math] і [math] S_y [/ math]), в нове безліч. Покладається що до виконання операції зазначені безлічі не перетиналися. Представником утвореного в результаті безлічі є довільний елемент [math] S_x \ cup S_y [/ math]. Оскільки необхідно, щоб безлічі були непересічними, операція UNION повинна знищувати безлічі [math] S_x [/ math] і [math] S_y [/ math].
FIND_SET (x) повертає покажчик на представника безлічі, в якому міститься елемент x.