Изменения
Нет описания правки
|<tex>O(n)</tex>
|}
<!-- Введем массив s, в s[i] будет храниться номер множества, к которому принадлежит i. Этот номер является идентификатором множества. Тогда find, очевидно, будет работать за <tex>O(1)</tex>.-->Пусть в массиве s хранятся номера множеств, в s[i] будет храниться номер множества, к которому принадлежит i. Этот номер отождествляет множество, find возвращает именно его. Тогда find, очевидно, будет работать за <tex>O(1)</tex>.
Чтобы объединить множества x и y, надо изменить все s[i], равные номеру множества x, на номер y. Тогда union работает за <tex>O(n)</tex>.
