Система неперетинних множин це структура даних (також звана структурою даної пошуку перетину або безліччю пошуку злиття), яка управляє безліччю елементів, розбитих на кілька підмножин, що не перетинаються. Вона надає близько-константний час виконання операцій (обмежений зворотною функцією Акерманна) за додаванням нових множин, *злиття існуючих множин і *випередження, чи відносяться елементи до одного і того ж безлічі.
Застосовується для зберігання компонентів зв'язності в графах, зокрема, алгоритму Фарбала необхідна подібна структура даних для ефективної реалізації.
Основні операції:
- MakeSet(x) - створює одноелементне безліч {x},
- Find(x) - повертає ідентифікатор множини, що містить елемент x,
- Union(x,y) - об'єднання множин, що містять x та y.
Після деяких операцій об'єднання, деякі множини зібрані разом.