Задача Задача №3472751
А
А
В компьютерной игре главный герой перемещается по государству, состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого.…
Запрос пользователя
В компьютерной игре главный герой перемещается по государству, состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого. Герой обошёл все острова в поисках карты, пройдя по каждому мосту ровно один раз. Но на острове Тёмном он побывал целых 9 раз. Сколько мостов ведёт с острова Темного, если герой не с него начал и не на нём закончил свой поход?
18
Пояснение:
- В эйлеровом маршруте, который проходит по каждому ребру ровно один раз и не начинается/не заканчивается на данной вершине, каждый раз, когда вершина проходит через неё (не как стартовая или конечная), маршрут входит в неё по одной дуге и выходит по другой. То есть используется две incident-рядыеEdges на такую посещение.
- Значит число посещений вершины = deg(вершины) / 2.
- Темная не является стартом и не является концом маршрута, значит каждая из её 9 посещений соответствуют прохождению через неё, и deg(Темного) = 2 * 9 = 18.
Итак, у Темного 18 мостов.
