Изменения

Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i</tex>. Этот номер отождествляет множество, <math> \mathrm{find } </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.

Чтобы объединить множества <tex> x </tex> и <tex> y</tex>, надо изменить все <tex> s[i]</tex>, равные номеру множества <tex> x</tex>, на номер <tex> y</tex>. Тогда union работает за <tex>O(n)</tex>.<code> '''int ''' s[n] '''func''' init(): '''for ''' i = 0 '''to ''' n - 1: s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве</font></code> <code> '''int''' find(k): '''return ''' s[k] </code><code> '''func''' union(x, y): '''if ''' s[x] == s[y]: '''return''' '''else:'''

'''for ''' i = 0 '''to ''' n - 1: '''if ''' s[i] == t: