223
правки
Изменения
Нет описания правки
{{В разработке}}
Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find)
==Реализация==
==Асимптотика==
! m*get + n*union || m*a(m,n) + n
|}
где m - общее количество операций, n - полное количество элементов, a(m, n) - функция, обратная функция к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой. Таким образом, при этой реализации время работы линейно зависит от количества операций.
==Ссылки==