Алгоритм проезжаемости одностороннего движения

В одном городе A есть серьезная проблема с парковкой саней, потому что они не имеют достаточно места на улицах.
Было принято решение исправить эту проблему таким образом, чтобы все улицы были с односторонним движением второе направление, чтобы определить парковку, надеясь таким образом обеспечить достаточное количество парковочных мест, причем с любого перекркстка можно добраться до любого другого, и поэтому город проходим. То что между некоторыми местами дорога будет дольше абсолютно не имеет значение.
Необходимо написать алгоритм на контроль проезжаемости города, который работает в линейном времени по отношению к количеству улиц. Помощь Чарли предложить этот алгоритм. Можем предпологать, что до введения улиц с односторонним движением можно быть от любого перекрестка, добраться до любого другого.
Необходимо
Выразить проблему которую надо решить такую ​​проблему на график таким образом, чтобы размер графа в соответствовал линейно числу улиц в городе (описать как задание проблемы пнревести на граф в размере линейно относительно к количеству улиц).
Идея и псевдокод-алгоритма, который на вашем графе представления проверяет, что город проходим. Этот алгоритм должен иметь линейную временную сложность из-за размера представления графа выбранной в первой части.
Вся сложность обосновать и обосновать корректность и перевод алгоритма (т.е. обосновать, что всякий раз, когда город с односторонним проездом от любого перекрестка на все остальные проездной, так что ваш алгоритм подтвердит это, и всякий раз, когда он не проходим, опровергнет).
Помогите!

0