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

Задача:

Есть неориентированный граф из вершин, изначально не содержащий рёбер. Требуется обработать запросов трёх типов:

[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].

написать про уровни и остовные леса [math]\mathrm{navernoe.}[/math]