1632
правки
Изменения
м
<code>
</code><code>
</code><code>
</code>
<code> '''srtructstruct''' nameOfStruct SetItem '''int ''' data '''SetItem''' head *nameOfStruct '''SetItem''' next int data'''SetItem''' tail
nameOFStruct '''SetItem''' s[n]
s[i].head = s[i]</code> <code> '''int''' find(nameOfStruct '''SetItem''' x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
</code> <code> '''func''' union(nameOfStruct '''SetItem''' x, nameOfStruct '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
</code>
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]
rollbackEdits.php mass rollback
Чтобы объединить множества <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]
'''if''' s[i] == t
s[i] = s[x]
=== С помощью списка ===
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.
'''func''' init():
'''for''' i = 0 '''to''' n - 1
s[i].data = i
s[i].head = s[i]
s[i].tail = s[i]
s[i].next = null
'''return''' x.head.data
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_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/ Система непересекающихся множеств и её применения]
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
