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

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