Изменения
→С помощью списка
=== С помощью списка ===
Пусть каждое множество хранится в виде списка. Вначале создается n списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на родительский следующий элемент(parentnext) и ссылку на хвост(tail). Тогда для объединения множеств надо будет просто перекинуть ссылку parent next на хвост начало другого множества. Таким образом, <tex> union </tex> работает за <tex> O(1) </tex>.
Для того, чтобы найти элемент в одном из множеств, надо идти по parentnext'ам, пока он не указывает на Null - тогда мы нашли элемент-представитель. Таким образом, <tex> find </tex> работает за <tex> O(n) </tex>.
Псевдокод:
init():
for i = 0 to n - 1:
s[i].set = i
s[i].parent next = Null
s[i].tail = s[i]
find(x)://подразумевается, что x - ссылка на один из элементов
while x.parent next != Null:
x = x.parent
return x.set
return
else:
y.parent next = x.tail
x.tail = y.tail
