Главная › Информатика › №23 · Графы: пути

ЕГЭ информатика, задание 23: №23 · Графы: пути

Дан ориентированный граф без циклов (рёбра): А→Б, Б→В, В→Г, В→Д, В→Е, Г→Д, Г→Ж, Д→Е, Д→Ж, Д→З, Е→З, Ж→И, Ж→К, З→К, И→К, И→Л, К→М, Л→М. Сколько существует различных путей из вершины А в вершину М, проходящих через вершину З?

Показать ответ и разбор
Ответ: 5

Идём по вершинам в порядке букв и для каждой складываем число путей во все вершины, из которых в неё ведут рёбра. Ответ: 5. Это новое задание ЕГЭ-2027: граф без циклов позволяет считать всё за один проход.

Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot

Ещё задания по теме