Сколько путей из А в К в графе с односторонними дорогами

Решение по шагам

1. 1

   Шаг 1. Что именно считаем

   Путь — это последовательность посёлков, в которой каждый следующий соединён с предыдущим дорогой в разрешённом направлении. Движение одностороннее: если есть дорога А→Б, то проехать из Б в А нельзя, и такие «обратные» варианты в подсчёт не идут.

   Введём обозначение: $N(X)$ — количество различных путей из А в посёлок $X$. Нам нужно $N(К)$.

2. 2

   Шаг 2. Правило суммирования

   В посёлок $X$ можно въехать только из тех посёлков, откуда в него ведёт дорога, — назовём их предшественниками. Любой путь до $X$ — это путь до какого-то предшественника плюс последняя дорога, поэтому $N(X)$ равно сумме значений $N$ по всем предшественникам $X$.

   Старт: $N(А)=1$ (в саму А ведёт «пустой» путь). Считать вершины надо в таком порядке, чтобы все предшественники уже были посчитаны: А, Б, В, Г, Д, Е, Ж, К — в этом списке все дороги ведут только вперёд.