Система неперетинних множин ( або DSU, також використовують назви , ) — структура даних, яка дозволяє відстежувати множину елементів, розбиту на неперетинні підмножини. При цьому кожній підмножині призначається її представник — елемент цієї підмножини.
Структура даних надає такі можливості. Спочатку є кілька елементів, кожен з яких знаходиться в окремій (своїй власній) множині. За одну операцію можна об'єднати дві будь-які множини, а також можна запитати, в якій множині зараз знаходиться зазначений елемент. У класичному варіанті вводиться ще одна операція — створення нового елемента, який поміщається в окрему множину — синґлетон.
Таким чином, базовий інтерфейс даної структури даних складається всього з трьох операцій:
MakeSet — додання нового елемента; розміщення його в нову множину, що складається з одного нього; Union — об'єднання двох зазначених множин; Find — повернення значення, в якій множині знаходиться зазначений елемент. Насправді при цьому повертається один з елементів множини званий представником () або лідером (leader). Цей представник вибирається в кожній множині самою структурою даних (і може змінюватися з плином часу). Наприклад, якщо виклик для якихось двох елементів повернув одне і те ж значення, то це означає, що ці елементи знаходяться в одній і тій же множині, а в іншому випадку — в різних множинах.
Описувана нижче структура даних дозволяє робити кожну з цих операцій майже за в середньому (більш докладно про асимптотику див. нижче після опису алгоритму).
Також в одному з підрозділів статті описаний альтернативний варіант реалізації DSU, що дозволяє домогтися асимптотики в середньому на один запит.
Побудова ефективної структури даних Визначимося спочатку, в якому вигляді ми будемо зберігати всю інформацію.
Множину елементів ми будемо зберігати у вигляді дерев: одне дерево відповідає одній множині. Корінь дерева — це представник (лідер) множини.
При реалізації це означає, що ми заводимо масив, в якому для кожного елемента зберігаємо посилання на його предка в дереві. Для коренів дерев будемо вважати, що їх предок — вони самі (тобто посилання зациклюється в цьому місці).
Наївна реалізація Ми вже можемо написати першу реалізацію системи неперетинних множин. Вона буде досить неефективною, але потім ми покращимо її за допомогою двох прийомів, отримавши в результаті майже константний час роботи.
Отже, вся інформація про множини елементів зберігається у нас за допомогою масиву parent.
Щоб створити новий елемент (операція make_set(v)), ми просто створюємо дерево з коренем у вершині, зазначаючи, що її предок — це вона сама.
Щоб об'єднати дві множини (операція union_set(a, b)), ми спочатку знайдемо лідерів першої і другої множини. Якщо лідери збіглися, то нічого не робимо — це означає, що множини і так вже були об'єднані. В іншому випадку можна просто вказати, що предок першої вершини дорівнює другій (або навпаки) — тим самим приєднавши одне дерево до іншого.
Реалізація операції пошуку лідера (find_set(v)) проста: ми піднімаємося по предкам від вершини, поки не дійдемо до кореня. Цю операцію зручніше реалізувати рекурсивно (особливо це буде зручно пізніше, у зв'язку з доданими оптимізаціями).
void make_set (int v) { parent[v] = v;
int find_set (int v) { if (v == parent[v]) return v; return find_set (parent[v]);
void union_sets (int a, int b) { a = find_set (a); b = find_set (b); if (a != b) parent[b] = a; }
Утім, така реалізація системи неперетинних множин дуже неефективна. Легко побудувати приклад, коли після кількох об'єднань множин вийде ситуація, що множина — це дерево, звиродніле в довгий ланцюжок. У результаті кожен виклик буде працювати на такому тесті за час порядку глибини дерева, тобто за .
Це дуже далеко від тієї асимптотики, яку ми збиралися отримати (константний час роботи). Тому розглянемо дві оптимізації, які дозволять (навіть застосовані окремо) значно прискорити роботу.
Евристика стиснення шляху Ця евристика призначена для прискорення роботи find_set().
Вона полягає в тому, що коли після виклику ми знайдемо шуканого лідера множини, то запам'ятаємо, що у вершині v і всіх пройдених по шляху вершин — саме цей лідер. Найпростіше це зробити, перенаправивши їх parent[] на цю вершину.
Таким чином, у масиву предків parent сенс дещо змінюється: тепер це стислий масив предків, тобто для кожної вершини там може зберігатися не безпосередній предок, а предок предка, предок предка предка, і т. д.
З іншого боку, зрозуміло, що не можна зробити, щоб ці покажчики parrent завжди вказували на лідера: інакше при виконанні операції довелося б оновлювати лідерів у елементів.
Таким чином, до масиву слід підходити саме як до масиву предків, можливо, частково стиснутого.
Нова реалізація операції має такий вигляд:
int find_set (int v) { if (v == parent[v]) return v; return parent[v] = find_set (parent[v]);
Така проста реалізація робить все, що задумувалося: спочатку шляхом рекурсивних викликів знаходиться лідера множини, а потім, в процесі розкрутки стека, цей лідер присвоюється parent посиланнями для всіх пройдених елементів.
Реалізувати цю операцію можна і не рекурсивно, але тоді доведеться здійснювати два проходи по дереву: перший знайде шуканого лідера, другий — проставить його всім вершин шляху. Втім, на практиці нерекурсивна реалізація не дає істотного виграшу.
Евристика об'єднання за рангом Розглянемо іншу евристику, яка сама по собі здатна прискорити час роботи алгоритму, а в поєднанні з евристикою стиснення шляхів і зовсім здатна досягти практично константного часу роботи на один запит в середньому.
Ця евристика полягає в невеликій зміні роботи union_set: якщо в наївній реалізації те, яке дерево буде приєднано до якого, визначається випадково, то тепер ми будемо це робити на основі рангів.
Є два варіанти рангової евристики: в одному варіанті рангом дерева називається кількість вершин в ньому, в іншому — глибина дерева (точніше, верхня межа на глибину дерева, оскільки при одночасному застосуванні евристики стиснення шляхів реальна глибина дерева може зменшуватися).
В обох варіантах суть евристики одна й та ж: при виконанні union_set будемо приєднувати дерево з меншим рангом до дерева з великим рангом.
void make_set (int v) { parent[v] = v; size[v] = 1;
void union_sets (int a, int b) { a = find_set (a); b = find_set (b); if (a != b) { if (size[a] < size[b]) swap (a, b); parent[b] = a; size[a] += size[b];
Наведемо реалізацію рангової евристики на основі глибини дерев:
void make_set (int v) { parent[v] = v; rank[v] = 0;
void union_sets (int a, int b) { a = find_set (a); b = find_set (b); if (a != b) { if (rank[a] < rank[b]) swap (a, b); parent[b] = a; if (rank[a] == rank[b]) ++rank[a];
Обидва варіанти рангової евристики є еквівалентними з точки зору асимптотики, тому на практиці можна застосовувати будь-яку з них.
Об'єднання евристик: стиснення шляху плюс рангова евристика Як вже згадувалося вище, спільне застосування цих евристик дає особливо гарний результат, у підсумку досягаючи практично константного часу роботи.
Доведення асимптотики тут не наводиться через їх об'ємність (див., наприклад, Кормен, Лейзерсон, Ривест, Штайн «Вступ до алгоритмів»). Вперше це доведення було проведено Тарджаном (1975 р.).
Остаточний результат такий: при спільному застосуванні евристик стиснення шляху та об'єднання за рангом час роботи на один запит виходить в середньому, де — обернена функція Акермана, яка зростає дуже повільно, настільки повільно, що для всіх розумних обмежень вона не перевершує 4 (приблизно для n <= 10600).
Саме тому про асимптотику роботи системи неперетинних множин доречно говорити «майже константний час роботи».
Наведемо тут підсумкову реалізацію системи неперетинних множин, що реалізує обидві вказані евристики (використовується рангова евристика щодо глибин дерев):
void make_set (int v) { parent[v] = v; rank[v] = 0;
int find_set (int v) { if (v == parent[v]) return v; return parent[v] = find_set (parent[v]);
void union_sets (int a, int b) { a = find_set (a); b = find_set (b); if (a != b) { if (rank[a] < rank[b]) swap (a, b); parent[b] = a; if (rank[a] == rank[b]) ++rank[a];
Застосування в задачах і різні поліпшення Структури даних неперетинних множин моделюють розбиття множини. Як відомо, розбиття множини можна задати за допомогою задання на ній відношення еквівалентності. І, навпаки, кожному відношенню еквівалентності заданому на деякій множині відповідає розбиття цієї множини. Це означає, що структура даних «система неперетинних множин» широко використовується. Наприклад, можна відстежувати компоненти зв’язаності неорієнтованого графа. Алгоритм Union–Find використовується у високопродуктивних реалізаціях уніфікації.
У цьому розділі розглянуто кілька застосувань структури даних «система неперетинних множин», як тривіальних, так і з використанням деяких поліпшень структури даних.
Підтримка компонент зв'язності графа Це одна з очевидних програм структури даних «система неперетинних множин», яка, вочевидь, і стимулювала вивчення цієї структури.
Формально задачу можна сформулювати таким чином: спочатку заданий порожній граф, поступово в цей граф можуть додаватися вершини і неорієнтовані ребра, а також надходять запити — «чи в однакових компонентах зв'язності лежать вершини і?».
Безпосередньо застосовуючи тут описану вище структуру даних, ми отримуємо рішення, яке обробляє один запит на додавання вершини / ребра або запит на перевірку двох вершин — за майже константний час у середньому.
Враховуючи, що практично таке саме завдання ставиться при використанні алгоритму Крускала знаходження мінімального кістякового дерева, ми відразу ж отримуємо поліпшену версію цього алгоритму, що працює практично за лінійний час.
Іноді на практиці зустрічається інвертована версія цього завдання: спочатку є граф з якимись вершинами і ребрами, і надходять запити на видалення ребер. Якщо завдання дане в офлайн, тобто ми заздалегідь можемо дізнатися всі запити, то вирішувати це завдання можна таким чином: перевернемо завдання задом наперед: будемо вважати, що у нас є порожній граф, в який можуть додаватися ребра (спочатку додамо ребро останнього запиту, потім передостаннього, і т. д.). Тим самим у результаті інвертування цього завдання ми прийшли до звичайної задачі, рішення якої описувалося вище.
Пошук компонент зв'язності на зображенні
Одне з очевидних застосувань DSU полягає у вирішенні такого завдання: є зображення пікселів; спочатку все зображення біле, але потім на ньому малюється декілька чорних крапок. Потрібно визначити розмір кожної «білої» компоненти зв'язності на підсумковому зображенні.
Для рішення ми просто перебираємо всі білі клітини зображення, для кожної клітини перебираємо її чотирьох сусідів, і якщо сусід теж білий — то викликаємо від цих двох вершин. Таким чином, у нас буде DSU з вершинами, відповідними пікселям зображення. Отримані в результаті дерева DSU — і є шукані компоненти зв'язності.
Підтримка додаткової інформації для кожної множини «Система неперетинних множин» дозволяє легко зберігати будь-яку додаткову інформацію, що відноситься до множини.
Простий приклад — це розміри множин: як їх зберігати, було сказано при описі рангової евристики (інформація там записувалася для поточного лідера множини).
Таким чином, разом з лідером кожної множини можна зберігати будь-яку додаткову необхідну в конкретному завданні інформацію.
Втім, таке рішення за допомогою системи неперетинних множин не має жодних переваг перед рішенням з допомогою обходу в глибину.
Застосування DSU для стиснення «стрибків» по відрізку. Завдання про зафарбування підвідрізків в офлайні Одне з поширених застосувань DSU полягає в тому, що якщо є набір елементів, і з кожного елемента виходить по одному ребру, тож ми можемо швидко (за майже константний час) знаходити кінцеву точку, в яку ми потрапимо, якщо будемо рухатися вздовж ребер із заданої початкової точки.