MST и DSU

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

Таймс, 4 этаж

Описание

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