Пути в графе без перебора

Пути в графе без перебора В задачах на пути не обязательно выписывать каждый маршрут. Можно считать прямо на схеме. В стартовой вершине А ставим 1: это 1 способ начать движение. Для каждой следующей вершины складываем количества способов из всех вершин, откуда идут входящие стрелки. До В можно дойти напрямую из А или через Б: 1 + 1 = 2 пути. До Г приходят 1 способ из Б и 2 из В: 1 + 2 = 3. До Д приходят 2 способа из В и 3 из Г: 2 + 3 = 5 маршрутов. Метод работает в графе без циклов, если предыдущие вершины уже посчитаны. Не меняй направление стрелок. https://academy-s.ru/ #информатика #программирование #огэ #егэ #репетитор