MST и DSU

Пятница, 25 ноября 2016

Таймс, 4 этаж

Описание

DSU на списках за $O(m + n\log n)$ (с доказательством)
DSU на ссылках к корню за $O((m+n)A^{-1}(n,m))$
Алгоритм Краскала (сортировка + DSU)
Алгоритм Прима (аналог Дейкстры)
Доказываем $O(\log*n)$ на запрос для второго из DSU