Изменения

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

{| class="wikitable" border="1" |<tex>init</tex> |<tex>find</tex> |<tex>union</tex>

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

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

int colors[n]

colors[i] = i //сначала каждый элемент лежит в своем множестве

return colors[k]

if colors[x] == colors[y]:

t = colors[y]

if colors[i] == t: colors[i] = colors[x]

{| class="wikitable" border="1" |<tex>init</tex> |<tex>find</tex> |<tex>union</tex>

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

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

find(x): //подразумевается, что x {{ - -- }} ссылка на один из элементов

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

x.next = y.head //соединили списки y.head = x.head //сделали корректную ссылку на голову для представителя нового списка

Два списка до операции <tex>union</tex>:

Два списка после операции <tex>union</tex>: