Есть ориентированный граф. Все края только в одном направлении. Проблема состоит в том, чтобы найти минимальное количество возможных изменений, чтобы вы могли переходить от одного данного узла к другому.
Например:
Для графа с тремя узлами и двумя ребрами (1-> 2, 3-> 2). Вам необходимо определить, сколько изменений в направлении ребра необходимо сделать, чтобы достичь пути от узла 1 к узлу 3. Ответом будет 1, поскольку достаточно изменить ребро 2-> 3 и получить путь 1-> 2- > 3.
Это задание с ограниченным временем (5 с). Количество точек и ребер находится в диапазоне [1,10 ^ 6]. Объем памяти ограничен 256 мегабайтами
Пожалуйста, помогите с поиском быстрого алгоритма для решения этой задачи