Изменения
Нет описания правки
Работа с DSU займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log V)</tex>.
==Литература==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
==См. также==
* [[Алгоритм Прима]]
