Question

В старину между азиатскими городами были охраняемые караванные пути: Дамаск – Багдад, Анкара –Дамаск, Стамбул – Тегеран, Самарканд – Иерусалим, Стамбул – Багдад, Каир – Иерусалим, Стамбул – Анкара, Дубай – Каир, Самарканд – Каир, Иерусалим – Дубай, Дамаск – Тегеран. До каких городов можно было безопасно добраться из Стамбула пользуясь только этими путями? Все пути двусторонние.
Дамаск
Самарканд
Тегеран
Иерусалим
Дубай
Багдад
Каир
Анкара

Answer 1

Ответ:

Дамаск

Тегеран

Багдад

Анкара

Объяснение:

Построим граф по предложенному списку дорог. Дороги будут ребрами, а города вершинами.

Как видим некоторые в некоторые города (вершины) нельзя попасть, потому что они находятся в другом компоненте связности графа. И нет дороги соединяющей эти два компонента.

Значит выбираем только те города (вершины), которые лежат в одном компоненте связности со Стамбулом.