[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Author Message
Mihail Eskov

Topics: 5
Messages: 17

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


______________________
=====
 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,062