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