В некотором царстве каждый город соединён с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

Рассмотрим условие. В царстве имеется n городов, между любыми двумя городами существует дорога. Король хочет назначить каждой дороге направление так, чтобы из любого города, выехав, нельзя было вернуться обратно. Это условие означает, что в получившемся ориентированном графе не должно быть циклов, то есть граф должен быть ациклическим.

Шаг 1. Понимание задачи.
Имеется полный неориентированный граф (каждая пара городов соединена) с n вершинами, и нам нужно назначить направление каждой...