117
правок
Изменения
→С помощью массива
Здесь будет пример работы
== Реализации ==
=== С помощью массива "цветов" ===Оценка работы:
{| border="1"
|<tex>init</tex>
|<tex>O(n)</tex>
|}
Введем массив s<tex>color</tex>, в <tex> scolor[i] </tex> будет храниться номер цвет множества, к которому принадлежит <tex>i</tex>. Тогда <tex> find </tex>, очевидно, будет работать за <tex> O(1) </tex>.
Чтобы объединить множества a <tex>x</tex> и b<tex>y</tex>, надо изменить все <tex> scolor[i] </tex>, равные aцвету <tex>x</tex>, на bцвет <tex>y</tex>. Тогда <tex> union </tex> работает за <tex> O(n) </tex>.
Псевдокод:
int scolor[n]
init():
for i = 0 to scolor.size - 1: scolor[i] = i//сначала каждый элемент лежит в своем множестве
find(k):
return scolor[k]
union(x, y):
if scolor[x] == scolor[y]:
return
else:
t = scolor[y] for i = 0 to scolor.size - 1: if scolor[i] == t: color.s[i] = scolor[x]
=== С помощью списка ===
