Задание 9 · Повышенный уровень · Модели и графы
Схемы и количество путей
Считаем количество маршрутов в ориентированной схеме.
Теория
Для ориентированного ациклического графа удобно подписывать у каждой вершины число путей из старта. Для старта ставим 1, для каждой следующей вершины складываем значения всех её предшественников.
Что держать в голове
ways(start)=1
ways(v)=сумма ways(u) по всем рёбрам u→v
Рёбра учитываются только по направлению стрелки
Алгоритм решения
- Найдите стартовую вершину.
- Поставьте в ней 1.
- Двигайтесь по направлению рёбер.
- В каждой вершине складывайте числа на входах.
Мини-пример
S→A, S→B, A→T, B→T: до A и B по одному пути, до T — 2.
Проверь себя
Есть рёбра S→A, S→B, A→C, B→C, C→T. Сколько путей из S в T?