Изменения

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

Псевдокод<!--'''Оценка работы:'''{| class="wikitable" border="1" |init |find |union |- |<tex>O(n)</tex> |<tex>O(1)</tex> |<tex>O(n)</tex> |}--> Пусть в массиве 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 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:

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

Псевдокод:Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <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  list '''SetItem''' s[n]  '''func''' init(): '''for ''' i = 0 '''to ''' n - 1: s[i].set data = i s[i].parent head = Nulls[i]

find(x)://подразумевается, что x - ссылка на один из элементов while x.parent != Null: x = x.parent return x.set union(x, y)[[Категория://теперь x Дискретная математика и y - номера множеств.алгоритмы]] if x == y[[Категория: return else: s[xСтруктуры данных].parent = s[y]