Изменения

Введем массив s, в s[i] будет храниться номер множества, к которому принадлежит i. Тогда find , очевидно, будет работать за O(1). Чтобы объединить множества a и b, надо изменить все s[i], равные a, а на b. Тогда union - работает за O(n), где n - количество множеств.

Пусть каждое множество хранится в виде списка. Вначале создается n списков, по одному элементов в каждом, для котором каждый элемент является представителем своего множества. Для каждого списка мы храним head и tail. В каждом элементе списка есть ссылка будем хранить ссылку на следующий родительский элемент(nextparent) и ссылка ссылку на headхвост(parenttail). Тогда для объединения множеств надо будет просто дать перекинуть ссылку с head'а одного списка parent на tail хвост другогомножества. Таким образом, union происходит работает за O(1). Для того, чтобы найти элемент в одном из множеств, надо идти по parent'ам, пока он не указывает на Null. Тогда - тогда мы нашли head и можем сказать, в каком множестве находится элемент-представитель. Тогда Таким образом, find работает за O(n).

union(x, y)://теперь здесь важно, что x и y - номера представители множеств.

s[y.parent = x.tail x].parent tail = s[y].tail