Мости: остання битва#4326
Чи має ваша дипломна робота практичне застосування?
_____________________________________________________
Популярне запитання
Легенда
Сергій наближається до завершення своєї дипломної роботи. З грудня тема залишається незмінною: "Задача про динамічну двохреберну зв'язність". Алгоритм розроблено, протестовано, і його складність O(K \log K) доведено. Тепер залишилося лише написати розділ про "практичне застосування".
Але яке ж може бути практичне застосування "Задачі про динамічну двохреберну зв'язність"? Це непросте питання — можливо, навіть важче за саму задачу. Проте диплом треба захищати, тому відповідь потрібна терміново.
Тож ось практичне застосування: за цією темою можна скласти задачу для олімпіади!
Задача
Дано неорієнтований граф із кількістю вершин до 10^5. Спочатку граф не містить жодного ребра. Вам потрібно обробити запити виду ADD та DEL — додавання або видалення ребра між вершинами та .
У будь-який момент необхідно визначити, скільки мостів наразі є у графі.
У графі ніколи не буває кратних ребер або петель.
Якщо надходить команда "видалити ребро", гарантовано, що відповідне ребро існує у графі в цей момент.
Підказки
Дипломна робота і називається "дипломною", бо її не можна написати лише за 5 годин. Тож ось 5 підказок:
Додавайте й видаляйте ребра — зробіть ребро "активним" на певному часовому відрізку.
Використайте підхід "Розділяй і володарюй".
Стискуйте двозв'язні компоненти.
Навіть після стискання двозв'язних компонент, якщо кількість запитів невелика, граф ще можна більше спростити.
Існує розв'язок за O(K \log K).
У першому рядку два цілих числа і : кількість вершин і кількість запитів відповідно (1 \le N \le 10^5, 1 \le K \le 10^5).
У наступних рядках кожен запит має формат, описаний нижче. Кожен запит починається зі слова ADD або DEL — для додавання чи видалення ребра відповідно. Після цього записано два цілих числа і — кінці ребра (1 \le a, b \le N, a \ne b).
Після кожного запиту виведіть одне ціле число — поточну кількість мостів у графі.
Приклад 1