Задача о динамической связности

Материал из Викиконспекты
Перейти к: навигация, поиск
Задача:
Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов:
  • [math]\mathrm{add(u,v)}[/math] — добавить ребро между вершинами [math]u[/math] и [math]v[/math],
  • [math]\mathrm{remove(u,v)}[/math] — удалить ребро между вершинами [math]u[/math] и [math]v[/math],
  • [math]\mathrm{connected(u,v)}[/math] — проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.


Динамическая связность в лесах

Если задача такова, что в графе нет и не может быть циклов, то её можно решить при помощи деревьев эйлерова обхода. Нужно только... читать продолжение в источнике.

Время работы для упрощённой задачи — [math]O(\log n)[/math].

Обобщение задачи для произвольных графов

написать про уровни и остовные леса


См. также

Источники информации