Мости: остання битва
А у Вашої дипломної є практичне застосування?
_____________________________________________________
Популярне питання
Легенда
Хлопчик Сергій вже майже завершив роботу над дипломною роботою. Тема диплому з грудня не змінилась, це усе ще "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.
Вихідні дані
Після кожного запиту потрібно вивести одне число - скільки у поточному графі мостів.