Как мы видим, получившийся граф, состоит из двух связных компонент. Для любых двух вершин из связной компоненты существует путь из одной в другую и не существует путь из вершины этой компоненты в вершину, ей не принадлежащую.
Можно особо не вдаваясь в теорию, просто глядя на граф, сказать, что города 1 и 9 между собой связей не имеют. А вот города 2 и 8 связаны, хоть и не напрямую, а с "пересадкой".
Answers & Comments
Для большей наглядности в решении построим граф.
Вершины графа - города, а рёбра - авиалинии.
Увидеть граф можно в приложении.
Как мы видим, получившийся граф, состоит из двух связных компонент. Для любых двух вершин из связной компоненты существует путь из одной в другую и не существует путь из вершины этой компоненты в вершину, ей не принадлежащую.
Можно особо не вдаваясь в теорию, просто глядя на граф, сказать, что города 1 и 9 между собой связей не имеют. А вот города 2 и 8 связаны, хоть и не напрямую, а с "пересадкой".
Ответ: из 1 в 9 - нет, из 2 в 8 - да.