Изменения

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

Если у нас есть набор чисел от 0 до N - 1, то ''система непересекающихся множеств Определены две операции:* <math> \mathrm{union(disjoint set unionx, DSUy)'' позволяет объединять их в } </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|Пример работы СНМ]]

Пусть в массиве 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>

Чтобы объединить множества x и y, надо изменить все '''int''' find(k): '''return''' s[ik], равные номеру множества x, на номер y. Тогда union работает за <tex>O(n)</tex>.

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

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

<!--'''Оценка работы:'''

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

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того, чтобы найти элемент в одном из множествпредставителя, надо идти нужно перейти по ссылкам next, пока он не указывает ссылке на null <tex> head </tex>. Значит <math> \mathrm{{ --- find}} тогда мы нашли элемент-представитель. Таким образом, find </math> работает за <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 <math> \mathrm{{ --- union}} ссылка на один из элементов while x.next != null: x = x.next return x.set union</math> работает за <tex> O(x, yn): /</ здесь важно, что x и y {{ --- }} представители множеств if x == y: return else: x.next = ytex>.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></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/ Система непересекающихся множеств и её применения]