Изменения

{{Определение| definition ='''Система (лес, объединение) непересекающихся множеств ''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{ --- }} иерархическая структура данных, поддерживающая операции <tex>union(x, y)</tex> {{ --- }} объединения множеств, содержащих <tex>x</tex> и <tex>y</tex>, и <tex>find(k)</tex> {{ --- }} поиск множества, которому принадлежит элемент <tex>k</tex>позволяющая эффективно работать с множествами.}} 

[[Файл:DSU_1_Example.png|600px500px|thumb|rightcenter|Пример работыСНМ]]

{| class="wikitable" border="1" |<tex>init</tex> |<tex>find</tex> |<tex>union</tex>

Введем массив <tex-->color</tex>, в <tex>color[i]</tex> будет храниться цвет множества, к которому принадлежит <tex>i</tex>. Тогда <tex>find</tex>, очевидно, будет работать за <tex>O(1)</tex>.

Чтобы объединить множества <tex>x</tex> и <tex>y</tex>Пусть в массиве s хранятся номера множеств, надо изменить все в <tex>colors[i]</tex>будет храниться номер множества, равные цвету к которому принадлежит <tex>xi </tex>. Этот номер отождествляет множество, на цвет <texmath>y\mathrm{find} </texmath>возвращает именно его. Тогда <texmath>union\mathrm{find} </texmath> работает , очевидно, будет работать за <tex>O(n1)</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''' int colors[n] '''func''' init(): '''for ''' i = 0 '''to ''' n - 1: colors[i] = i <font color=green> //сначала каждый элемент лежит в своем множестве</font> '''int''' find(k): '''return color''' s[k] '''func''' union(x, y): '''if color''' s[x] == colors[y]: '''return''' '''else:''' t = colors[y] '''for ''' i = 0 '''to ''' n - 1: '''if color''' s[i] == t: colors[i] = colors[x]

<!--'''Оценка работы:'''{| class="wikitable" border="1" |<tex>init</tex> |<tex>find</tex> |<tex>union</tex>

|}Пусть каждое множество хранится в виде списка. Вначале создается <tex-->n</tex> списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на следующий элемент <tex>(next)</tex> и ссылку на голову (<tex>head</tex>). Тогда для объединения множеств надо будет просто перекинуть ссылку <tex>next</tex> на начало другого множества. Таким образом, <tex>union</tex> работает за <tex>O(1)</tex>.

Будем хранить множество в виде списка. Для того, чтобы найти каждого элемента списка храним ссылку на следующий элемент в одном из множеств, надо идти по ссылкам и указатель на <tex>nexthead </tex>, пока он не указывает который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex>nullhead </tex> {{ --- }} тогда мы нашли элемент-представитель. Таким образом, Значит <texmath>\mathrm{find} </texmath> работает за <tex>O(n1)</tex>.

Псевдокод: s[n] init(): for i = 0 to n - 1: s[i].set = i s[i].next = null s[i].Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head = s[i] find(x): <//подразумеваетсяtex>. Таким образом, что x - ссылка на один из элементов while x.next != null: x = x.next return x.set <math> \mathrm{union} </math> работает за <tex> O(x, yn): /</здесь важно, что x и y - представители множеств if x == y: return else: xtex>.next = y.head //соединили списки y.head = x.head //сделали корректную Чтобы объединить два списка, нужно хранить ссылку на голову для представителя нового <tex> tail </tex>. Ее можно хранить в голове списка.

'''Пример работы:struct'''SetItem '''int''' data '''SetItem''' head '''SetItem''' next '''SetItem''' tail

'''func''' init(): '''for''' i = 0 '''to''' n - 1 s[i].data = i s[Файл:DSU_1_Xi].head = s[i] s[i].pngtail = s[i] s[i].next = null

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

Два списка после операции '''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font> x = x.head y = y.head '''if''' x == y '''return''' x.tail.next = y <font color=green> // соединим списки </font> x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex>union</font> '''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex>:</font> y.head = x y = y.next

[[Файл:DSU_1_XYDSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]

* [[СНМ(списки с весовой эвристикой)]]* [[СНМ(реализация с помощью леса корневых деревьев)]]

== Источники информации ==*[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/ Система непересекающихся множеств и её применения]