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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У даній статті розглядається структура даних "система непересічних множин" (англійською "disjoint-set-union", або просто "DSU").

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

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

  • Додає новий елемент, поміщаючи його в нову множину, що складається з одного нього;
  • Об'єднує дві зазначених множини;
  • Повертає, в якій множині знаходиться зазначений елемент. Насправді при цьому повертається один з елементів множини (званий представником або лідером (в англомовній літературі "leader")). Цей представник вибирається в кожній множині самою структурою даних (і може змінюватися з плином часу).

Наприклад, якщо виклик для якихось двох елементів повернув одне і те ж значення, то це означає, що ці елементи знаходяться в одній і тій же множині, а в іншому випадку - в різних множинах.

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

Також в одному з підрозділів статті описаний альтернативний варіант реалізації DSU, що дозволяє домогтися асимптотики в середньому на один запит при О(log N);

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

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

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

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

Наївна реалізація[ред.ред. код]

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

Отже, вся інформація про множини елементів зберігається у нас за допомогою масиву parrent.

  • Щоб створити новий елемент (операція 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;
}

Втім, така реалізація системи непересічних множин дуже неефективна. Легко побудувати приклад, коли після кількох об'єднань множин вийде ситуація, що множина - це дерево, звиродніле в довгий ланцюжок. У результаті кожен виклик буде працювати на такому тесті за час порядку глибини дерева, тобто за О(n).

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

Евристика стиснення шляху[ред.ред. код]

Ця евристика призначена для прискорення роботи find_set().

Вона полягає в тому, що коли після виклику ми знайдемо шуканого лідера множини, то запам'ятаємо, що у вершині v і всіх пройдених по шляху вершин - саме цей лідер. Найпростіше це зробити, перенаправивши їх parrent[] на цю вершину.

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

З іншого боку, зрозуміло, що не можна зробити, щоб ці покажчики parrent завжди вказували на лідера: інакше при виконанні операції довелося б оновлювати лідерів у елементів.

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

Нова реалізація операції виглядає наступним чином:

int find_set (int v) {
	if (v == parent[v])
		return v;
	return parent[v] = find_set (parent[v]);

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

Реалізувати цю операцію можна і нерекурсивно, але тоді доведеться здійснювати два проходи по дереву: перший знайде шуканого лідера, другий - проставить його всім вершин шляху. Втім, на практиці нерекурсивна реалізація не дає істотного виграшу.

Евристика об'єднання за рангом[ред.ред. код]

Розглянемо тут іншу евристику, яка сама по собі здатна прискорити час роботи алгоритму, а в поєднанні з евристикою стиснення шляхів і зовсім здатна досягти практично константного часу роботи на один запит в середньому.

Ця евристика полягає в невеликій зміні роботи 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 р.).

Остаточний результат такий: при спільному застосуванні евристик стиснення шляху та об'єднання за рангом час роботи на один запит виходить O(A(n)) в середньому, де A(n) - обернена функція Акермана, яка зростає дуже повільно, настільки повільно, що для всіх розумних обмежень вона не перевершує 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];
	}
}

Застосування в задачах і різних поліпшення[ред.ред. код]

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

Підтримка компонент зв'язності графа[ред.ред. код]

Це одне з очевидних програм структури даних "система непересічних множин", яке, по всій видимості, і стимулювало вивчення цієї структури.

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

Безпосередньо застосовуючи тут описану вище структуру даних, ми отримуємо рішення, яке обробляє один запит на додавання вершини / ребра або запит на перевірку двох вершин - за майже константне час в середньому.

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

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

Пошук компонент зв'язності на зображенні[ред.ред. код]

Одне з лежачих на поверхні застосувань DSU полягає у вирішенні наступного завдання: є зображення пікселів. Спочатку все зображення біле, але потім на ньому малюється декілька чорних крапок. Потрібно визначити розмір кожної "білої" компоненти зв'язності на підсумковому зображенні.

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

Підтримка додаткової інформації для кожного множини[ред.ред. код]

"Система непересічних множин" дозволяє легко зберігати будь-яку додаткову інформацію, що відноситься до множини.

Простий приклад - це розміри множин: як їх зберігати, було описано при описі рангової евристики (інформація там записувалася для поточного лідера множини).

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

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

Застосування DSU для стиснення "стрибків" по відрізку. Завдання про зафарбування підвідрізків в офлайні[ред.ред. код]

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

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

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

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

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

Реалізація:

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 парність стане рівною a\oplus b. (символом \oplus. тут позначена операція XOR (симетрична різниця)). Нам потрібно, щоб ці дві парності розрізнялися, тобто їх XOR дорівнював одиниці. Тобто отримуємо рівняння на t:

~
x \oplus y \oplus t.

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

~
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 (мінімум на відрізку) за в середньому в офлайні[ред.ред. код]

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

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

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

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

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

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