Изменения

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

__TOC__Определены две операции:* <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|center|Пример работы СНМ]]

Чтобы объединить множества a и b<!--'''Оценка работы:'''{| class="wikitable" border="1" |init |find |union |- |<tex>O(n)</tex> |<tex>O(1)</tex> |<tex>O(n)</tex> |}--> Пусть в массиве s хранятся номера множеств, надо изменить все в <tex> s[i] </tex>будет храниться номер множества, равные aк которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, на b<math> \mathrm{find} </math> возвращает именно его. Тогда <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 ''' s[n] '''func''' init(): '''for ''' i = 0 '''to s.size ''' 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 s.size ''' n - 1: '''if ''' s[i] == t:

Пусть каждое множество хранится в виде списка. Вначале создается <!--'''Оценка работы:'''{| class="wikitable" border="1" |init |find |union |- |<tex>O(n списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на следующий элемент(next) и ссылку на хвост(tail). Тогда для объединения множеств надо будет просто перекинуть ссылку next на начало другого множества. Таким образом, </tex> |<tex> union O(n)</tex> работает за |<tex> O(1) </tex>. |}-->

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того, чтобы найти элемент в одном из множествпредставителя, надо идти нужно перейти по next'ам, пока он не указывает ссылке на Null - тогда мы нашли элемент-представитель<tex> head </tex>. Таким образом, Значит <texmath> \mathrm{find } </texmath> работает за <tex> O(n1) </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  '''SetItem''' s[n]  '''func''' init(): '''for ''' i = 0 '''to ''' n - 1: s[i].set data = i s[i].next head = Nulls[i]

s[i].next = null  '''int''' find('''SetItem''' x): <font color=green> //подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов while x.next != Null: x = x.parent return x.set union(x, y):/</здесь важно, что x и y - представители множествfont> if x == y: '''return else: y.next = ''' x.tail x.tail = yhead.taildata

Два списка до операции '''func''' union('''SetItem''' x, '''SetItem''' y):<font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>[[Файл:1 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></font> '''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font> y.head = x y = y.GIF]]next

Два списка после операции union:[[Файл:2DSU_list_example.GIFpng|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/ Система непересекающихся множеств и её применения]* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава V-2221.

[http[Категория://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств Дискретная математика и её примененияалгоритмы]][[Категория: Структуры данных]]