Что: Лекция
Когда: Пятница, 25 ноября 2016, 18:30–20:00
Где: Таймс, 4 этаж

Описание

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