Система неперетинних множин

Система неперетинних множин (англ. disjoint-set-union або DSU, також використовують назви англ. union–find data structure, англ. merge–find set) — структура даних, яка дозволяє відстежувати множину елементів, розбиту на неперетинні підмножини. При цьому кожній підмножині призначається її представник — елемент цієї підмножини.

Додані 8 елементів.

Після декількох операцій об'єднання, деякі множини згруповані.

Структура даних надає такі можливості. Спочатку є кілька елементів, кожен з яких знаходиться в окремій (своїй власній) множині. За одну операцію можна об'єднати дві будь-які множини, а також можна запитати, в якій множині зараз знаходиться зазначений елемент. У класичному варіанті вводиться ще одна операція — створення нового елемента, який поміщається в окрему множину — синґлетон.

Таким чином, базовий інтерфейс даної структури даних складається всього з трьох операцій:

• MakeSet — додання нового елемента; розміщення його в нову множину, що складається з одного нього;
• Union — об'єднання двох зазначених множин;
• Find — повернення значення, в якій множині знаходиться зазначений елемент. Насправді при цьому повертається один з елементів множини званий представником (англ. representative) або лідером (leader). Цей представник вибирається в кожній множині самою структурою даних (і може змінюватися з плином часу). Наприклад, якщо виклик для якихось двох елементів повернув одне і те ж значення, то це означає, що ці елементи знаходяться в одній і тій же множині, а в іншому випадку — в різних множинах.

Описувана нижче структура даних дозволяє робити кожну з цих операцій майже за ${\displaystyle O(1)}$ в середньому (більш докладно про асимптотику див. нижче після опису алгоритму).

Також в одному з підрозділів статті описаний альтернативний варіант реалізації DSU, що дозволяє домогтися асимптотики ${\displaystyle O(\log N)}$ в середньому на один запит.

Побудова ефективної структури даних

Визначимося спочатку, в якому вигляді ми будемо зберігати всю інформацію.

Множину елементів ми будемо зберігати у вигляді дерев: одне дерево відповідає одній множині. Корінь дерева — це представник (лідер) множини.

При реалізації це означає, що ми заводимо масив, в якому для кожного елемента зберігаємо посилання на його предка в дереві. Для коренів дерев будемо вважати, що їх предок — вони самі (тобто посилання зациклюється в цьому місці).

Наївна реалізація

Ми вже можемо написати першу реалізацію системи неперетинних множин. Вона буде досить неефективною, але потім ми покращимо її за допомогою двох прийомів, отримавши в результаті майже константний час роботи.

Отже, вся інформація про множини елементів зберігається у нас за допомогою масиву 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; } 

Утім, така реалізація системи неперетинних множин дуже неефективна. Легко побудувати приклад, коли після кількох об'єднань множин вийде ситуація, що множина — це дерево, звиродніле в довгий ланцюжок. У результаті кожен виклик буде працювати на такому тесті за час порядку глибини дерева, тобто за ${\displaystyle O(n)}$.

Це дуже далеко від тієї асимптотики, яку ми збиралися отримати (константний час роботи). Тому розглянемо дві оптимізації, які дозволять (навіть застосовані окремо) значно прискорити роботу.

Евристика стиснення шляху

Ця евристика призначена для прискорення роботи 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 р.).

Остаточний результат такий: при спільному застосуванні евристик стиснення шляху та об'єднання за рангом час роботи на один запит виходить ${\displaystyle O(A(n))}$ в середньому, де ${\displaystyle A(n)}$ — обернена функція Акермана, яка зростає дуже повільно, настільки повільно, що для всіх розумних обмежень вона не перевершує 4 (приблизно для n <= 10⁶⁰⁰).

Саме тому про асимптотику роботи системи неперетинних множин доречно говорити «майже константний час роботи».

Наведемо тут підсумкову реалізацію системи неперетинних множин, що реалізує обидві вказані евристики (використовується рангова евристика щодо глибин дерев):

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 полягає в тому, що якщо є набір елементів, і з кожного елемента виходить по одному ребру, тож ми можемо швидко (за майже константний час) знаходити кінцеву точку, в яку ми потрапимо, якщо будемо рухатися вздовж ребер із заданої початкової точки.

Наочним прикладом цього застосування є завдання про фарбування підвідрізків: є відрізок довжини L, кожна клітинка якого (тобто кожен шматочок довжини 1) має нульовий колір. Надходять запити виду — (l, r,c) перефарбувати відрізок [l;r] в колір c. Потрібно знайти підсумковий колір кожної клітинки. Запити вважаються відомими заздалегідь, тобто завдання — в офлайні.

Для рішення ми можемо завести DSU-структуру, яка для кожної клітини буде зберігати посилання на найближчу справа непофарбовану клітинку. Таким чином, спочатку кожна клітинка вказує на саму себе, а після фарбування першого підвідрізка — клітинка перед початком підвідрізка буде вказувати на клітинку після кінця підвідрізка.

Тепер, щоб вирішити завдання, розглядаємо запити перефарбовування у зворотному порядку: від останнього до першого. Для виконання запиту кожного разу з допомогою нашого DSU знаходимо найлівішу непофарбовану клітинку всередині відрізка, перефарбовуєм її, і перекидаємо покажчик з неї на наступну справа порожню клітинку.

Таким чином, тут фактично використовуємо DSU з евристикою стиснення шляхів, але без рангової евристики (тому нам важливо, хто стане лідером після об'єднання). Отже, підсумкова асимптотика складе ${\displaystyle O(logN)}$ на запит (утім, з маленькою у порівнянні з іншими структурами даних константою).

Реалізація:

void init() { for (int i=0; i<L; ++i) make_set (i); }   void process_query (int l, int r, int c) { for (int v=l; ; ) { v = find_set (v); if (v >= r) break; answer[v] = c; parent[v] = v+1; } } 

Утім, можна реалізувати це рішення з ранговою евристикою: будемо зберігати для кожної множини в деякому масиві end[], де множина закінчується (тобто саму праву точку). Тоді можна буде об'єднувати дві множини в одну за їх ранговою евристикою, проставляючи потім отриману нову праву межу.

Підтримка відстаней до лідера

Іноді в конкретних програмах системи неперетинних множин з'являється вимога підтримувати відстань до лідера (тобто довжину шляху в ребрах у дереві від поточної вершини до кореня дерева).

Якби не було евристики стиснення шляхів, то ніяких складнощів не виникало б — відстань до кореня просто дорівнювало б числу рекурсивних викликів, які зробила функція find_set.

Проте в результаті стиснення шляхів кілька ребер шляху могли стиснутися в одне ребро. Таким чином, разом з кожною вершиною доведеться зберігати додаткову інформацію: довжину поточного ребра з вершини в предка.

При реалізації зручно уявляти, що масив parrent[] і функція find_set тепер повертають не одне число, а пару чисел: вершину-лідера і відстань до неї:

void make_set (int v) { parent[v] = make_pair (v, 0); rank[v] = 0; }   pair<int,int> find_set (int v) { if (v != parent[v].first) { int len = parent[v].second; parent[v] = find_set (parent[v].first); parent[v].second += len; } return parent[v]; }   void union_sets (int a, int b) { a = find_set (a) .first; b = find_set (b) .first; if (a != b) { if (rank[a] < rank[b]) swap (a, b); parent[b] = make_pair (a, 1); if (rank[a] == rank[b]) ++rank[a]; } } 

Підтримка парності довжини шляху і завдання про перевірку двочасткового графа в онлайн

За аналогією з довжиною шляху до лідера, так само можна підтримувати парність довжини шляху до нього. Чому ж це застосування було виділено в окремий пункт?

Справа в тому, що зазвичай вимога зберігання парності шляху спливає у зв'язку з наступною задачею: спочатку дан порожній граф, в нього можуть додаватися ребра, а також надходити запити виду «чи є компонента зв'язності, що містить дану вершину, двочастковою?».

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

Головна складність, з якою ми стикаємося при цьому, — це те, що ми повинні акуратно, з урахуванням парності, проводити об'єднання двох дерев у функції union_sets.

Якщо ми додаємо ребро (a, b), що пов'язує дві компоненти зв'язності в один, то при приєднанні одного дерева до іншого ми повинні вказати йому таку парність, щоб в результаті у вершин a і b виходили б різні парності довжини шляху.

Виведемо формулу, за якою повинна виходити ця парність, що виставляється лідеру однієї множини при приєднанні його до лідера іншої. Позначимо через x парність довжини шляху від вершини a до лідера її множини, через y — парність довжини шляху від b вершини до лідера її множини, а через t — шукану парність, яку ми повинні поставити приєднуваному лідеру. Якщо множина з вершиною a приєднується до множини з вершиною b, стаючи піддеревом, то після приєднання у вершини b її парність не зміниться і залишиться рівною y, а у вершини a парність стане рівною ${\displaystyle a\oplus b.}$ (символом ${\displaystyle \oplus .}$ тут позначена операція XOR (симетрична різниця)). Нам потрібно, щоб ці дві парності розрізнялися, тобто їх XOR дорівнював одиниці. Тобто отримуємо рівняння на t:

${\displaystyle ~x\oplus y\oplus t.}$

вирішуючи яке, знаходимо:

${\displaystyle ~t=x\oplus y\oplus 1.}$

Таким чином, незалежно від того, яка множина приєднується до якої, треба використовувати зазначену формулу для задання парності ребра, проведеного з одного лідера до іншого.

Наведемо реалізацію DSU з підтримкою парності. Як і в попередньому пункті, з метою зручності ми використовуємо пари для зберігання предків і результату операції find_set. Крім того, для кожної множини ми зберігаємо в масиві bipartite[], чи є воно все ще двочастковим чи ні.

void make_set (int v) { parent[v] = make_pair (v, 0); rank[v] = 0; bipartite[v] = true; }   pair<int,int> find_set (int v) { if (v != parent[v].first) { int parity = parent[v].second; parent[v] = find_set (parent[v].first); parent[v].second ^= parity; } return parent[v]; }   void add_edge (int a, int b) { pair<int,int> pa = find_set (a); a = pa.first; int x = pa.second;   pair<int,int> pb = find_set (b); b = pb.first; int y = pb.second;   if (a == b) { if (x == y) bipartite[a] = false; } else { if (rank[a] < rank[b]) swap (a, b); parent[b] = make_pair (a, x ^ y ^ 1); if (rank[a] == rank[b]) ++rank[a]; } }   bool is_bipartite (int v) { return bipartite[ find_set(v) .first ]; 

Алгоритм знаходження RMQ (мінімуму на відрізку) в офлайні

Формально завдання ставиться так: потрібно реалізувати структуру даних, яка підтримує два види запитів: додавання вказаного числа ${\displaystyle insert(i).(i=1..n)}$ і пошук і витяг поточного мінімального числа ${\displaystyle extractmin()}$. Будемо вважати, що кожне число додається рівно один раз.

Крім того, вважаємо, що вся послідовність запитів відома нам заздалегідь, тобто завдання — в офлайні.

Ідея рішення така. Замість того, щоб по черзі відповідати на кожен запит, переберемо число ${\displaystyle i=1..n}$, і визначимо, відповіддю на який запит це число повинне бути. Для цього нам треба знайти перший без відповіді запит, що йде після додавання ${\displaystyle insert(i)}$ цього числа — легко зрозуміти, що це і є той запит, відповіддю на який є число.

Таким чином, тут виходить ідея, схожа на завдання про фарбування відрізків.

Можна отримати рішення за в середньому ${\displaystyle O(\log N)}$ на запит, якщо ми відмовимося від рангової евристики і будемо просто зберігати в кожному елементі посилання на найближчий справа запит ${\displaystyle extract\ min()}$, і використовувати стиснення шляхів для підтримки цих посилань після об'єднань.

Також можна отримати рішення і за ${\displaystyle O(a(n))}$, якщо ми будемо використовувати рангову евристику і будемо зберігати в кожній множині номер позиції, де вона закінчується (те, що в попередньому варіанті рішення досягалося автоматично за рахунок того, що посилання завжди йшли тільки вправо, — тепер треба буде зберігати явно).

Історія

У той час як ідеї, використані в системі неперетинних множин були давно знайомі, Роберт Тарджан був першим, хто довів верхню межу (і обмежену версію нижньої межі) у термінах зворотної функції Аккермана, у 1975 році. До цього найкращою межею на час роботи за операцію був, доведений Гопкрофтом і Ульманом, ${\displaystyle O(\log *n)}$, повторний логарифм n, інша повільно зростаюча функція (але зростаюча не так повільно, як зворотня функція Аккермана).

Тарджан і ^[en] також розробили однопрохідний алгоритм пошуку, який є більш ефективним на практиці, зберігаючи ту ж складність у гіршому випадку.

У 2007 році Сільвен Коншон і Жан-Крістоф Фільят розробили варіант напів^[en] для системи неперетинних множин, що дозволив ефективно зберегти попередні версії структури, та було доведено його правильність за допомогою засобу доведення теорем Coq.

Див. також

• Розбиття множини
• ^[en]
• ^[en]

Посилання

1. Knight, Kevin (1989). Unification: A multidisciplinary survey (PDF). ACM Computing Surveys. 21: 93—124. doi:10.1145/62029.62030. S2CID 14619034.
2. Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM. 22 (2): 215—225. doi:10.1145/321879.321884. {{}}: Cite має пусті невідомі параметри: |1=, |2=, |3= та |4= ()
3. Set Merging Algorithms. SIAM Journal on Computing. 2 (4): 294—303. doi:10.1137/0202024. {{}}: Cite має пустий невідомий параметр: |1= ()
4. Worst-case analysis of set union algorithms, Journal of the ACM, 31 (2), 1984: 245—281, doi:10.1145/62.2160 {{}}: Cite має пусті невідомі параметри: |1= та |2= ()
5. A Persistent Union-Find Data Structure, ACM SIGPLAN Workshop on ML, Freiburg, Germany {{}}: |first= з пропущеним |last= (); Cite має пусті невідомі параметри: |1= та |2= ()

Джерела

• Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
• C++ implementation, частина Boost C++ бібліотек
• A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
• Java applet: A Graphical Union–Find Implementation, від Rory L. P. McGuire
• Wait-free Parallel Algorithms for the Union–Find Problem, стаття 1994 року від Richard J. Anderson і Heather Woll описує розпаралелену версію операцій Union-Find, які не потребують блокування
• Реалізація на пайтоні
• Візуальне пояснення і C# код
• https://www.geeksforgeeks.org/disjoint-set-data-structures/