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

Задача:

Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов: добавить ребро между вершинами [math]u[/math] и [math]v[/math], удалить ребро между вершинами [math]u[/math] и [math]v[/math], проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.

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

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

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

Обобщение задачи о динамической связности

А это уже сложнее)0)

См. также

• Деревья эйлерова обхода
• Задача о динамической связности оффлайн

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

• http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf
• Dynamic connectivity — Википедия
• http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf