@dalbio

Как быстро найти вершину,которая имеет наибольшее количество ребер и не соединена с данной вершиной?

Вся суть вопроса описана в названии,добавлю,что граф задаётся списком ребер.Как это сделать быстро,не перебором. (в некоторых случаях граф может быть деревом,мб это как-то поможет),сама задача:
https://acmp.ru/asp/do/index.asp?main=task&id_cour...
  • Вопрос задан
  • 639 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
В общем случае - никак. Никакого способа, кроме как просмотреть все вершины, не связанные с данной, нет.

Но обычно вам и не надо решать эту задачу один раз для конкретной вершины. Как в приведенной задаче - вам надо решить ее для всех вершин графа одновременно. Кроме того, в приведенной задаче граф - всегда дерево.

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

Но в этой задаче можно проще: Найдите все вершины с максимальной степенью. Если из 3 и более, то найдите среди них 2 не связанные (берете любую, потом еще одну любую. Если они связанны, то берите любую третью - она не связанна с одной из двух первых).

Если их 2, то проверьте, вдруг они не связанны. Если же они соседние или такая всего одна, то найдите в графе еще одну вершину с максимальной степенью, которая не связанна хотя бы с одной из этих двух. Чтобы это работало за линию - заведите массив и прибавьте 1 ко всем соседям каждой из 1/2 максимальных вершин. Потом смотрите на те, где стоит 0 (или 1, если максимальных две).

Также рассмотрите в качестве варианта ответа пару соседей для максимальной вершины, если она одна. Это выбрать в массиве 2 наибольших числа - делается за линию.

Почему это работает? Понятно, что в задаче надо найти пару не связанных вершин с максимальной суммой степеней. Очевидно, что в случае трех и более максимумов или двух несвязанных максимумов этот алгоритм даст самый оптимальный ответ - 2 наибольших числа в массиве. Лучше никак не сделать.

Теперь рассмотрим случай двух связанных максимальных вершин. Рассмотрим оптимальный ответ. Если в нем нет одной из максимальных вершин, то мы могли бы заменить один из концов на максимум. Мы не можем этого сделать, только если оба конца связанны с обоими максимумами, а это означало бы циклы в графе. Но у нас же дерево! Значит, оптимальный ответ обязательно содержит одну из максимальных вершин. Но мы этот вариант в алгоритме перебрали.

Остается случай из одной максимальной вершины. Опять же оптимальный ответ не содержит ее, только если его нельзя улучшить - а значит оба конца связанны с максимальной вершиной. Но этот случай мы тоже разобрали.
Ответ написан
@dalbio Автор вопроса
У задачи ограничение 2*10^5,так что этот вариант не подходит (сама задача:https://acmp.ru/asp/do/index.asp?main=task&id_cour...),мб я как-то не так понял условие
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы