Union-find, або система неперетинних множин (DSU), підтримує набір множин, що не перетинаються. Вона надає дві базові операції: find, яка повертає представника (корінь) множини, що містить елемент, і union, яка зливає дві множини, що містять два елементи. Два елементи належать одній множині саме тоді, коли в них спільний корінь.

Кожна множина зберігається як кореневе дерево в одному масиві parent[]. Кожен елемент вказує на свого батька, а корінь вказує сам на себе. Тож уся структура — це ліс дерев, по одному дереву на кожну неперетинну множину. Щоб перевірити зв'язність, кожен елемент проходять угору до кореня й порівнюють два корені.

Об'єднання за рангом приєднує нижче дерево під корінь вищого, тримаючи дерева мілкими. Ранг — це верхня межа висоти дерева. Коли в двох коренів однаковий ранг, один стає нащадком іншого, а ранг кореня, що залишився, зростає на одиницю. Це не дає лісу виродитися в довгий ланцюг.

Стиснення шляху застосовується під час find: після знаходження кореня кожен пройдений вузол перенаправляють напряму на цей корінь. Це сплющує дерево, тож майбутні запити до цих вузлів майже миттєві. Симуляція анімує це, підсвічуючи пройдений шлях, а потім перемальовуючи зі стиснутими вказівниками.

З об'єднанням за рангом і стисненням шляху послідовність із m операцій над n елементами виконується за O(m·α(n)), де α — обернена функція Аккермана. α(n) зростає настільки повільно, що для будь-якого практичного n вона менша за 5, тож кожна операція фактично сталого часу, хоча й не строго O(1).

Функція Аккермана зростає астрономічно швидко, тож її обернена α(n) зростає астрономічно повільно. Для будь-якого розміру входу, що міг би вміститися в спостережному Всесвіті, α(n) не перевищує 4. Саме тому амортизовану вартість union-find з обома оптимізаціями на практиці вважають по суті сталою.

Кількість неперетинних множин дорівнює кількості коренів у лісі. Спочатку маємо n одноелементних множин, тобто n компонент. Кожне успішне об'єднання двох різних множин зменшує кількість компонент рівно на одну. Це робить union-find ефективним способом відстежувати зв'язність графа в міру додавання ребер.

Алгоритм Краскала для мінімального кістякового дерева сортує ребра за вагою й додає кожне ребро лише тоді, коли його кінці в різних множинах, що перевіряється через find. Додавання ребра виконує union. Union-find робить це виявлення циклів майже сталим, тож Краскал працює за O(E log E), де домінує сортування.

Так. Рандомізована версія алгоритму Краскала будує ідеальні лабіринти: спочатку кожна клітинка — окрема множина, а стіни всюди, потім багаторазово прибирають випадкову стіну лише тоді, коли дві клітинки, які вона розділяє, у різних множинах, об'єднуючи їх. Це гарантує повністю зв'язний лабіринт без циклів.

Якщо find(a) і find(b) повертають той самий корінь, елементи вже зв'язані, тож union структурно нічого не робить, і кількість компонент не змінюється. Надійна реалізація виявляє це заздалегідь і пропускає оновлення рангу, уникаючи зайвої роботи й тримаючи ліс коректним.