Изменения
Нет описания правки
Запустив BFS от произвольной вершины. Мы получим дерево BFS.
Пусть нет, тогда взяв расстояние от <tex>w</tex> до глубочайшего листа мы можем улучшить ответ.
Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>bfs</tex>, очевидно что ей в пару надо сопоставить вершину <tex>w</tex> , что <tex>dist(u, w) - <tex>max</tex> {---} максимально. Очевидно, что проблема решается запуском bfs из <tex>u</tex>.
== Оценка производительности ==
Все операции кроме bfs - <tex>О(1)</tex>.
BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E).
