Алгоритмы и структуры данных поиска: Динамическая связность в графах. Бабенко Максим

822

Бабенко Максим рассказывает о динамической связности в графах.

  1. Задача о динамической связности: вставки и удаления ребер, запросы о связности.
  2. Частный случай задачи для случая лесов.
  3. Деревья эйлеровых обходов: слияние и разделение.
  4. Использование амортизации и набора лесов для решения со сложностью O(log^2 n).