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

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