Помогите с задачей
Здравствуйте!
Я решаю следующую задачу http://www.spoj.pl/problems/SAMER08I/
Ну собственно решаю следующим образом. Строю граф где вершины это конфедерации, а ребра - города. Тогда получается что нужно узнать существует ли в графе эйлеров цикл или эйлеров путь, и если да то вывести ребро с минимальным номером (ребро=город, номер ребра=номер города) с которого он может начаться. Для проверки сначала узнаю связный ли граф.Потом стандартно считаю степени вершин игнорируя петли. И если количество вершин с нечетной степенью больше 2 то решений нет. Если вершин с нечетной степенью нет, значит есть эйлеров цикл и можно начинать с любого ребра, поэтому вывожу самое минимальное - 0. А если есть две вершины с нечетной степенью, соответственно есть эйлеров путь. И вот тут с выбором ребра у меня возникли проблемы. Я сначала думал что можно просто взять ребро с минимальным номером у любой из двух вершин с нечетной степенью - но это не так. Если привести пример где есть 1 мост и 2 компоненты двусвязности, содержащие каждая более 1 вершины, то станет понятно что мост никак не может быть первым ребром в пути. Поэтому я нахожу все компоненты двусвязности и мосты, и проверяю если вершина с нечетной степенью находиться в компоненте двусвязности в которой больше 2 вершин то мост не может быть первым и я его не рассматриваю.
Собственно вопрос то в том что все это я никак не могу пропихнуть - выдает что ответ неверный. Мои рассуждения верны или не до конца? Если верны то буду в коде ошибки искать.
Я решаю следующую задачу http://www.spoj.pl/problems/SAMER08I/
Ну собственно решаю следующим образом. Строю граф где вершины это конфедерации, а ребра - города. Тогда получается что нужно узнать существует ли в графе эйлеров цикл или эйлеров путь, и если да то вывести ребро с минимальным номером (ребро=город, номер ребра=номер города) с которого он может начаться. Для проверки сначала узнаю связный ли граф.Потом стандартно считаю степени вершин игнорируя петли. И если количество вершин с нечетной степенью больше 2 то решений нет. Если вершин с нечетной степенью нет, значит есть эйлеров цикл и можно начинать с любого ребра, поэтому вывожу самое минимальное - 0. А если есть две вершины с нечетной степенью, соответственно есть эйлеров путь. И вот тут с выбором ребра у меня возникли проблемы. Я сначала думал что можно просто взять ребро с минимальным номером у любой из двух вершин с нечетной степенью - но это не так. Если привести пример где есть 1 мост и 2 компоненты двусвязности, содержащие каждая более 1 вершины, то станет понятно что мост никак не может быть первым ребром в пути. Поэтому я нахожу все компоненты двусвязности и мосты, и проверяю если вершина с нечетной степенью находиться в компоненте двусвязности в которой больше 2 вершин то мост не может быть первым и я его не рассматриваю.
Собственно вопрос то в том что все это я никак не могу пропихнуть - выдает что ответ неверный. Мои рассуждения верны или не до конца? Если верны то буду в коде ошибки искать.