Задание EGEINFCFF5FD: Подсчёт путей в графе

Путь определяется последовательностью дорог, а движение разрешено только по стрелкам. Для каждой вершины будем складывать количества путей, приходящих по разным последним дорогам: такие наборы не пересекаются.
Все города можно обработать в порядке А, В, Б, Г, Д, Ж, Е, К, И, Л: каждая дорога ведёт от более раннего города в этом списке к более позднему. Это также показывает, что вернуться в прежний город невозможно.
Пусть N(X) — число путей из А в X. Задаём N(А) = 1: единственный пустой начальный путь служит основой для продолжений. Для остальных городов складываем значения всех непосредственных предшественников.
N(В) = N(А) = 1.
N(Б) = N(А) + N(В) = 1 + 1 = 2.
N(Г) = N(А) + N(В) = 1 + 1 = 2.
N(Д) = N(Б) + N(В) = 2 + 1 = 3.
N(Ж) = N(В) + N(Г) = 1 + 2 = 3.
N(Е) = N(В) + N(Д) + N(Ж) = 1 + 3 + 3 = 7.
N(К) = N(Ж) = 3.
N(И) = N(Д) + N(Е) = 3 + 7 = 10.
N(Л) = N(Ж) + N(И) + N(К) = 3 + 10 + 3 = 16.
Независимо посчитаем продолжения с конца. Пусть Q(X) — число путей из X в Л. Начинаем с Q(Л) = 1; затем для каждого города складываем Q его непосредственных следующих городов.
Q(И) = Q(Л) = 1.
Q(К) = Q(Л) = 1.
Q(Е) = Q(И) = 1.
Q(Ж) = Q(Е) + Q(К) + Q(Л) = 1 + 1 + 1 = 3.
Q(Д) = Q(Е) + Q(И) = 1 + 1 = 2.
Q(Г) = Q(Ж) = 3.
Q(Б) = Q(Д) = 2.
Q(В) = Q(Б) + Q(Г) + Q(Д) + Q(Е) + Q(Ж) = 2 + 3 + 2 + 1 + 3 = 11.
Q(А) = Q(Б) + Q(В) + Q(Г) = 2 + 11 + 3 = 16.
Требуются все пути от начала до конца, поэтому ответ равен N(Л) = 16.
Проверка: общий подсчёт вперёд N(Л) = 16 совпадает с обратным Q(А) = 16. Оба направления учитывают каждую допустимую последовательность дорог ровно один раз.
Ответ: 16.