Изменения

''Система непересекающихся множеств (disjoint set union, DSU)'' Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1</tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.

* <math> \mathrm{union(x, y) } </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y</tex>* <math> \mathrm{find(x) } </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x</tex>Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find(x) } </math> и <math> \mathrm{find(y)} </math>.

[[Файл:DSU_1_Example.png|500px|left|thumbcenter|Пример работы СНМ]]<br clear="all"/>

Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i</tex>. Этот номер отождествляет множество, <math> \mathrm{find } </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.

Чтобы объединить множества <tex> x </tex> и <tex> y</tex>, надо изменить все <tex> s[i]</tex>, равные номеру множества <tex> x</tex>, на номер <tex> y</tex>. Тогда <math> \mathrm{union } </math> работает за <tex>O(n)</tex>.

'''int ''' s[n] '''func''' init(): '''for ''' i = 0 '''to ''' n - 1: s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве</font> '''int''' find(k): '''return ''' s[k] '''func''' union(x, y): '''if ''' s[x] == s[y]: '''return''' '''else:'''

'''for ''' i = 0 '''to ''' n - 1: '''if ''' s[i] == t:

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head</tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head</tex>. Значит <math> \mathrm{find } </math> работает за <tex> O(1) </tex>. Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.  '''struct''' SetItem '''int''' data '''SetItem''' head '''SetItem''' next '''SetItem''' tail

Для объединения множеств потребуется объединить два списка и обновить ссылки на head. Таким образом, union работает за <tex> O( '''SetItem''' s[n) </tex>.Чтобы объединить два списка, нужно хранить ссылку на tail. Ее можно хранить в голове списка.]

s[n] '''func''' init(): '''for ''' i = 0 '''to ''' n - 1:

s[i].head = s[i] '''int''' find('''SetItem''' x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов</font> '''return ''' x.head.data '''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>

'''if ''' x == y: '''return''' x.tail.next = y <font color=green> // соединим списки</font> x.tail= y.next tail <font color= y green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font> x.tail '''while''' y <tex> \neq </tex> null <font color= y.tail green> // скорректируем ссылки на <tex> head </tex> у элементов множества "<tex> y" while y != null:</tex> </font>

[[Файл:DSU_list_example.png|800px|left|thumbcenter|Пример объединения двух множеств (union)]]<br clear="all"/>

== Источники информации ==*[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2 Википедия {{---}} Система непересекающихся множеств]* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]