Изменения

Система непересекающихся множеств(disjoint set union, DSTDSU) - структура данных, поддерживающая операции <tex> union(x, y) </tex> - объединения множеств, содержащих x и y, и <tex> find(k) </tex> - поиск множества, которому принадлежит элемент k.

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

Чтобы объединить множества a и b, надо изменить все <tex> s[i]</tex>, равные a, на b. Тогда <tex> union </tex> работает за <tex> O(n)</tex>.

Пусть каждое множество хранится в виде списка. Вначале создается n списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на родительский элемент(parent) и ссылку на хвост(tail). Тогда для объединения множеств надо будет просто перекинуть ссылку parent на хвост другого множества. Таким образом, <tex> union </tex> работает за <tex> O(1)</tex>.

Для того, чтобы найти элемент в одном из множеств, надо идти по parent'ам, пока он не указывает на Null - тогда мы нашли элемент-представитель. Таким образом, <tex> find </tex> работает за <tex> O(n)</tex>.