Мосты: последняя битва
А у Вашей дипломной есть практическое применение?
_____________________________________________________
Популярный вопрос
Легенда
Мальчик Серёжа уже почти закончил работу над дипломной работой. Тема диплома с декабря не изменилась, это всё ещё "Dynamic 2-Edge-Connectivity Problem". Алгоритм уже придуман, протестирован, доказана оценка O(K log K)... Осталось только написать главу про "практическое применение".
Ну какое может быть практическое применение у задачи "Dynamic 2-Edge-Connectivity Problem"? Вопрос непростой. Он оказался чуть ли не сложнее исходной задачи. Но диплом нужно защитить, так что нужно срочно что-то делать.
Итак, первое практическое применение: можно предложить на соренование задачу на эту тему!
Задача
Дан неориентированный граф из не более чем 10^5 вершин. Изначально граф не содержит рёбер. Вам нужно обрабатывать запросы вида ADD x y и DEL x y - добавить или удалить ребро из x в y.
В каждый момент времени нужно знать, сколько в графе мостов.
Кратных рёбер и петель ни в какой момент времени нет.
Если поступает команда "удалить ребро", оно в графе точно присутствует.
Решение задачи
Диплом на то и диплом, что за 5 часов его так просто не напишешь. Поэтому Вам даны целых 5 подсказок:
Добавить ребро и удалить ребро - сделать ребро "живым" на некотором отрезке времени.
Используйте метод "Разделяй и Властвуй".
Сжимайте компоненты двусвязности.
Даже когда компоненты двусвязности уже сжаты, если запросов мало, граф всё ещё можно сильно уменьшить.
Существует решение за O(K log K).
Входные данные
В первой строке записаны целые числа N и K: количество вершин и количество запросов, соответственно. 1 ≤ N≤ 10^5, 1 ≤ K ≤ 10^5.
В следующих K строках по одному в строке записаны запросы. Каждый запрос начинается словом "ADD" или "DEL" для запроса на добавление или удаление ребра, соответственно. После этого слова два целых числа a и b, задающих ребро. 1 ≤ a, b ≤ N, a ≠ b.
Выходные данные
После каждого запроса нужно вывести одно число - сколько в текущем графе мостов.