Поиск радиуса графа.

Так он именно двудольный? То есть есть две доли, и рёбра только между ними?

Для начала, не очень точно дано определение диаметра графа
Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число ребер, которые необходимо пройти, чтобы добраться из одной вершины в другую.
Может это у вас диаметр,и можно ссылку на задачу откуда она взята?
Так же,вроде не существует пока что алгоритмов кроме самых быстрых лобовых(перебирая и с каждой вершины пуская алгоритм находа минимальных путей ),для двудольных думаю можно что нибудь откопать.

Ээээ, ну так ограничения нужны точные, а так можешь просто написать
Пускаем с каждой вершины поиск в ширину за O(V+E) V - кол-во вершин,E - кол-во рёбер.
И вычисляем ответ,сложно O(V) * O(V+E) = O(V^2 + VE)

Часом не этой задачи как таковой нету?)

Ярослав Так а можно решить задачу про поиск диаметра графа быстрее чем в лобовую?*:D

можно решить не в лоб.
кстати, количество ребер 4 * 10^4

Ну заливку то понятно что можно решить быстрее, иначе задачу бы не предлагали Правда мне почему-то кажется что не стоит ее обсуждать, т.к. олимпиада все-таки еще идет.

ну строим граф, "конденсируем его" и пускаем bfs из всех вершин.
но это дает ТЛ, поэтому пускаем bfs не из всех, а с каким-нибудь шагом.
можно еще отсортить вершины по кол-ву ребер и идти с середины : )

А что сделать то надо? Откуда в теме про радиус,вообще заливка появилась? Не понимаю.

Хм... Ну на эту задачу я попробовал написать заливку снаружи,то есть выбираю в какой цвет покрашу и начинаю это делать снаружи,так как слои окрашиваться будут именно так,и выбираю ответ минимальный..
Прошла с первого раза,сложность O(N * M).