| Dynamic Connectivity Training |
|---|
| Закончено |
Мальчик Серёжа уже почти закончил работу над дипломной работой. Тема диплома с декабря не изменилась, это всё ещё «Dynamic 2-Edge-Connectivity Problem». Алгоритм уже придуман, протестирован, доказана оценка
... Осталось только написать главу про «практическое применение».
Ну какое может быть практическое применение у задачи «Dynamic 2-Edge-Connectivity Problem»? Вопрос непростой. Он оказался чуть ли не сложнее исходной задачи. Но диплом нужно скоро защитить, так что срочно нужно что-то делать.
Итак, первое практическое применение: можно предложить на соревнование задачу на эту тему!
Дан неориентированный граф из не более чем 105 вершин. Изначально граф не содержит рёбер. Вам нужно обрабатывать запросы вида ADD x y и DEL x y — добавить или удалить ребро из x в y.
В каждый момент времени нужно знать, сколько в графе мостов.
Кратных рёбер и петель ни в какой момент времени нет.
Если поступает команда «удалить ребро», оно в графе точно присутствует.
Диплом на то и диплом, что за 5 часов его так просто не напишешь. Поэтому вам даны целых 5 подсказок.
. В первой строке записаны целые числа N и K: количество вершин и количество запросов, соответственно. 1 ≤ N ≤ 105, 1 ≤ K ≤ 105.
В следующих K строках по одному в строке записаны запросы. Каждый запрос начинается словом «ADD» или «DEL» для запроса на добавление или удаление ребра, соответственно. После этого слова записаны два целых числа a и b, задающих ребро. 1 ≤ a, b ≤ N, a ≠ b.
После каждого запроса нужно вывести одно число — сколько в текущем графе мостов.
4 8
ADD 1 2
ADD 2 3
ADD 1 3
DEL 2 3
DEL 1 2
ADD 2 4
ADD 1 4
ADD 2 3
1
2
0
2
1
2
3
0
| Название |
|---|


