nickitat's blog

By nickitat, 11 years ago, In Russian

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

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

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

  • добавить ребро (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/ там же в сборнике есть описание и видео с разбора где все хорошо рассказано."

  • Vote: I like it
  • +10
  • Vote: I do not like it