117
правок
Изменения
м
→С помощью массива "цветов"
== Реализации ==
=== С помощью массива "цветов" ===
'''Оценка работы:'''
{| class="wikitable" border="1"
|<tex>O(n)</tex>
|}
Введем массив s, в s[i] будет храниться цвет номер множества, к которому принадлежит i. Этот номер является идентификатором множества. Тогда find, очевидно, будет работать за <tex>O(1)</tex>.
Чтобы объединить множества x и y, надо изменить все s[i], равные цвету номеру множества x, на цвет номер y. Тогда union работает за <tex>O(n)</tex>.
'''Псевдокод:'''
