Вариант 2
Привет! Давай посмотрим, что у нас здесь за задание.
Так, у нас есть расписание рейсов авиакомпании для страны Цветной. Нужно построить граф, где вершины — это города, и соединять их ребрами только в случае, если есть авиарейс между этими городами. Задача — выяснить, существует ли в этом графе цикл.
Итак, по Варианту 2 (он у нас и выделен) нам нужно исследовать следующие города и рейсы:
- Дымчатый → Зелёный
- Дымчатый → Жёлтый
- Дымчатый → Коралловый
- Жёлтый → Амарантовый
- Коралловый → Бронзовый
Чтобы понять, есть ли цикл, нам нужно проследить, можно ли вернуться в исходный город, следуя последовательности рейсов.
Давай поступим так: начнём отслеживать маршруты из города Дымчатый, так как из него исходит больше всего рейсов.
Если мы вылетим из Дымчатого в Зелёный, то дальше у нас нет информации о рейсах из Зелёного, значит, этот путь дальше не приведёт к циклу.
Если мы вылетим из Дымчатого в Жёлтый, то из Жёлтого у нас есть рейс только в Амарантовый. Но дальше из Амарантового у нас информации нет, так что цикл не образуется.
3
