Схема дорог, связывающих населённые пункты А, Б, В, Г, Д, Е, представлена связным ориентированным графом. По каждой дороге можно двигаться только в указанном направлении. Сколько существует различных путей из пункта А в пункт Е, проходящих через пункт В?

Алгоритм решения задачи

Задача сводится к нахождению количества путей из вершины $A$ в вершину $E$, которые обязательно проходят через вершину $B$.

1. Дано

• Граф: Связный ориентированный граф с вершинами $\{A, Б, В, Г, Д, Е\}$.
• Условие: Движение возможно только по указанным направлениям рёбер.
• Требуется: Найти количество путей из $A$ в $E$, проходящих через $B$.

2. Найти

Количество путей $N(A \to B \to E)$.

3. Решение

Поскольку путь должен обязательно пройти через пункт $B$, мы можем разбить общую задачу на две независимые подзадачи:

1. Найти ко...