Том, Джеррі та незмінний план#13005

Том, Джеррі та незмінний план (Розбір)

Каркасне дерево зберігає всі мости й викидає рівно одне ребро з кожного незалежного циклу, причому вибір у різних двозв'язних компонентах (блоках) незалежний. Тому мультимножина степенів стала тоді й лише тоді, коли її не змінює жоден блок окремо: якщо якийсь блок дає два різні результати, зафіксувавши вибір у решті блоків, ми одразу отримаємо два каркасні дерева з різними мультимножинами.

Розберемо, які блоки нічого не змінюють.

Отже: знайти блоки (звичайний пошук у глибину зі стеком ребер), перевірити, що кожен — міст або цикл (кількість ребер дорівнює кількості вершин блоку), і що всі ребра кожного циклу з'єднують однакову пару степенів. Степені беруться у вихідному графі, а не всередині блока.

Складність: O(n + m).

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.