Question

В Волшебной стране есть 8 городов, пронумерованных числами от 1 до 8, и несколько дорог, соединяющих эти города. В связи с наступлением зимы на каждой дороге введено одностороннее движение. Король хочет перенести столицу страны в тот город, из которого можно добраться до всех остальных по этим дорогам, возможно, по пути проезжая через промежуточные города. Определите, в каком городе должна быть столица. В ответ запишите номер этого города (если вариантов ответа несколько, запишите наименьший номер).
Все дороги занесены в таблицу (см. рисунок), если на пересечении i-ой строки и j-ого столбца стоит 1, это означает, что из города с номером i ведет дорога в город с номером j (с направлением движения от i до j).

Answer 1

Ответ:

8

Объяснение:

смотри прикрепленные изображения:

• 1способ:

перебрать все города,и смотреть по построенному графу,можно ли попасть во все остальные

и замечаем,что только из 8 можно попасть во все остальные города

• 2способ:

заметить, что в город 8 нельзя никак попасть, а в остальные города из 8 можно, следовательно город 8 - будущая столица