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

Нужен непустой маршрут, начинающийся и заканчивающийся в Е. Промежуточное возвращение в Е запрещено, а остальные города нельзя посещать повторно. Поэтому считаем путь до первого возвращения в Е.
Временно уберём Е из промежуточной схемы. В оставшемся графе все стрелки идут вперёд в следующем порядке городов: В, А, Б, Г, Д, И, Л, К, Ж. Значит, в такой части маршрута повторить город невозможно: замкнутого обхода среди оставшихся вершин нет.
Обозначим N(X) число способов выйти из Е и дойти до 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(Д) = 3.
N(Л) = 1 + N(Д) + N(И) = 1 + 3 + 3 = 7.
N(К) = N(Л) = 7.
N(Ж) = N(Г) + N(К) + N(Л) = 2 + 7 + 7 = 16.
Вернуться в Е можно только последней дорогой из Г, Д, Ж. Поэтому число нужных маршрутов равно N(Г) + N(Д) + N(Ж) = 2 + 3 + 16 = 21.
Проверка по первой дороге: после Е → В число маршрутов равно 19; после Е → Л число маршрутов равно 2. Эти группы не пересекаются, а их сумма равна 21. Во всех них конец в Е считается единственным разрешённым повторением исходного города.
Ответ: 21.