Загальні відомості
Система неперескающіхся множин (англ. Disjointed set union, іноді union-find) - специфічна структура даних, яка містить інформацію про набір множин, яка дозволяє об'єднувати безлічі і відповідати на питання, чи належать зазначені елементи до одного безлічі.
Спочатку розглядаються N різних елементів, кожен з яких представляє собою самостійне безліч. Далі будь-які дві множини допустимо об'єднувати, при цьому всі елементи обох множин стають елементами результуючого безлічі. Очевидно, що з початкового стану (N одноелементні множин) через (N-1) злиття буде отримано стан, при якому всі елементи об'єднані в одне безліч. Як можна буде переконатися в подальшому, реалізації системи непересічних множин досить просто доповнити операцією додавання нового одноелементна безлічі (тобто додавання (N + 1) -го елемента, що формує самостійне безліч).
Будь-яке безліч може бути унікальним чином ідентифіковано за допомогою одного зі своїх елементів: два безлічі не можуть містити один і той же елемент за визначенням (цей факт відображений словом «непересічних» в назві структури даних). Такий елемент називається представником безлічі (англ. Representative element).
Тут і далі будемо припускати, що елементами множин є цілі числа. Система непересічних множин повинна забезпечувати наступні операції:
- визначення представника безлічі, якому належить елемент x. Очевидно, що якщо елементи x і y належать одному безлічі, то повинна виконуватися умова find (x) == find (y). В іншому випадку повинно мати місце find (x)! = Find (y);