Добрый вечер.

Поделитесь, пожалуйста, материалом о решении динамической задачи связности.

Конкретно интересует такая постановка вопроса: дана туча запросов вида

• добавить ребро (u, v)

• удалить ребро (u, v)

• вывести количество компонент связности на данный момент

Ограничения порядка 10^5 на количество вершин и количество запросов. Онлайн.

Впрочем, буду рад описанию решения любой вариации данной задачи.

Благодарю.

UPD Большое спасибо tiirz:

"Здесь есть авторское решение http://snpo.kture.kharkov.ua/files/2011/Disk%233/materials/Day5_16-02-11_Kopeliovich/Problems_sources/Problem_O_Hard/Solutions/ там же в сборнике есть описание и видео с разбора где все хорошо рассказано."