Изменения

Чтобы объединить множества <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>. Ее можно хранить в голове списка.

'''struct''' SetItem

'''int''' data

s[i].tail = s[i]

s[i].next = null

'''int''' find('''SetItem''' x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>

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

'''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>

x = x.head

y.head = x

y = y.next

[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]