Решение основывается на следующем правиле.
Правило сложения. Пусть дан ориентированный граф, не содержащий циклов, и
из вершины 
этого графа выходит 
ребра 
которые ведут
соответственно в вершины 
и 
Пусть далее из вершины 
в вершину 
ведет 
путей, из вершины в вершину ведет 
путей, из вершины 
в вершину ведет 
путей. Пусть 
– количество путей из вершины в
вершину 
Тогда Это правило, естественно, может быть переформулировано для любого
количества ребер, выходящих из данной вершины.
Имея в виду это правило, построим такую таблицу:
 |  |  | |  |  |  |  |  |  |  |  |
| Вершина |  |  |  |  |  |  |  |  |  |  |  |
| Куда выход | — | | | | | 
| | 
| 
| | 
 |
| К-во путей | | | | | | | | | | | |
Во второй строке перечислены вершины, в третьей для каждой вершины указано, куда ведут ребра, выходящие из этой вершины. В четвертой строке
будем записывать количество путей из каждой вершины в вершину 
эти
количества будем вычислять, пользуясь правилом сложения. Из самой вершины
есть ровно один путь в себя – это «пустой путь». Порядок обработки вершин определяется следующим правилом: к моменту
обработки вершины должно быть известно количество путей для всех вершин,
куда из данной вершины ведут ребра. Порядок, в котором вершины указаны в
таблице, этому правилу соответствует. Заполняя таблицу слева направо,
пользуясь правилом сложения, получим:
| | | | | | | | | | | |
| Вершина | | | | | | | | | | | |
| Куда выход | — | | | | |
| |
|
| |
|
| К-во путей | | | | | | | | | | |  |
По
каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
