Динамическая связность offline
Дополнительные главы алгоритмов, часть 1


Что: Лекция
Когда: Воскресенье, 07 декабря 2014, 13:00–14:30
Где: ПОМИ РАН

Описание

  • Связность. Ребра только добавляются. СНМ (DSU)
  • Корневая оптимизация, решение за \(O((n+k)\sqrt{n})\) в offline
  • Решение для Connectivity за \(O((k+n)\log k)\) в offline
  • Двухсвязность. Ребра только добавляются
  • Решение для 2-Connectivity за \(O((k+n)\log k)\) в offline
  • Решение задачи про MST: \(\max w - \min w \rightarrow \min\)

Задача про связность

http://www.e-olimp.com/en/problems/1881