Изменения

Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.

== Реализации ==

Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</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].next = null

'''return''' x.head.data

x = x.head

y = y.head

'''if''' x == y

'''return'''

y.head = x

y = y.next

== Другие реализации ==

== Источники информации ==

* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.

[[Категория: Дискретная математика и алгоритмы]]