Оптимальный алгоритм на графах

#графы

На графе существует две особые вершины: синяя и красная. Задача состоит в том, чтобы
при удалении красной вершины, также удалить все вершины из которых нельзя достичь синей,
т.е. граф как бы должен распасться на два, один из которых подлежит удалению.

Мое решение состоит в том, чтобы проверить существование пути из каждой вершины в
синюю. Если все пути очередной вершины проходят через красную, то производить удаление
этой вершины.

Может существует более оптимальное решение?




    

Ответы

Ответ 1

А если так: 


Удалить красную вершину и все ребра, примыкающие к ней.
В получившемся графе провести поиск в глубину из синей вершины. 


Найденная компонента связности и есть искомый результат.