http://acm.tju.edu.cn/toj/showp3404.html
Як зробити цю задачу?
Суть для мене понятна - поки можливо шукаєм найбільший шлях який проходить по кожному ребрі один раз (це буде дерево з n-1 ребер і n вершин послідовно з'єднаних). Ребра які ввійшли в цей шлях видаляєм з графа. До результату додаєм 1.
Проблема в тому, як таке реалізувати за 1 сек?
Можливо, є якийсь простіший розв'язок?
Підкажіть, будь ласка, алгоритм або виправте мене якщо я неправий. Спасибі.
Змінив(ла) Witaliy, 07-12-2009 17:29
Дякую за підказку, зрозумів.
А тепер більш реалізаційне питання: як зберігати граф (неорієнтований) так, щоб було зручно шукати довільну веришу, яка сполучена з V і видаляти ребро яке їх сполучає? Я спробував відсортований список ребер (M*2 ребер відсортованих по зростанню) - шукати зручно (за О(1)), але видаляти - ні, бо треба шукати два ребра (( A,B ) i ( B,A ). ( A, B ) найдеться за O(1), а з другим більш проблематично).
Як тут бути?
