Форум DL

Мой профиль

Sp59
BIA
Дан связанный ориентированный граф. Из вершины один есть путь во
все остальные вершины.
Требуется определить кол-во вершин графа при удалении которых
в графе появятся вершины НЕ достижимые из первой.
Вершин до 5000
Рёбер до 200000
10 тестов
Итак..."в лоб" это перебрать вершину и проверить граф на связанность.
(V*(V+E) т.е 5000*200000=10^9).
Были идеи по построению алгоритма по анологии с поиском мостов(или точек разрыва ) в НЕ ориентированом графе. Т.е. строить дерево поиска в глубину( пробовал и в ширину

) и считать динамику
для каждой вершины...но это не удавалось.
Идеи....?

______________________
=====