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

Question

[dalbio]

Вся суть вопроса описана в названии,добавлю,что граф задаётся списком ребер.Как это сделать быстро,не перебором. (в некоторых случаях граф может быть деревом,мб это как-то поможет),сама задача:
https://acmp.ru/asp/do/index.asp?main=task&id_cour...

Comments

[shurshur]

Не соединена непосредственно (соседство) или через промежуточные вершины? Рёбра однонаправленные или двунаправленные?

[dalbio]

Понял,удаляю пост

Answer 1

[Wataru]

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

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

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

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

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

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

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

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

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

Comments

[Роман]

Илья Николаевский помогите понять задачу)) Поясните пожалуйста по следующим вопросам. Дано, как я его вижу (если вижу не правильно поправьте пожалуйста)

1. Всей Галактике известна Всеобъемлющая Галактическая Магистральная Сеть, соединяющая многие звёздные системы между собой. Эта транспортная сеть объединяет n звёздных систем посредством n−1 магистралей — скоростных путей, соединяющих некоторые две звёздные системы между собой. Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети
я понял так:
1.1 магистраль - это ребро между 2-я вершинами?
1.2 маршрут - это последовательность магистралей, соединяющих любые 2 вершины?
1.3 любые 2 вершины имеют только 1 маршрут?
1.4 данный граф может быть только деревом, в котором любые 2 ветви могут быть соединены только через некоторую (единственную общую для них) развилку, находящуюся ближе к корню, относительно обоих ветвей?

2. Сложность постройки такой магистрали вызвано наличием развилок. Чтобы разгрузить транспортную сеть по максимуму, в любой звёздной системе существуют развилки. Развилки соединяют уникальным туннелем каждую пару магистралей, входящих в звёздную систему.
я понял так:
2.1 если вершина имеет 2 магистрали то развилка одна, если 3 магистрали то развилки уже 3, если m магистралей то количество развилок будет суммой чисел в интервале от m-1? (2 ребра = 1 развилка, 3 ребра 1+2 развилки, 4 ребра 1+2+3 развилки, 5 ребер 1+2+3+4 развилки и т.д.) То есть, количество развилок можно считать по формуле r=m*(m-1)/2, где m - число ребер у вершины?
2.2 если все вышесказанное правильно, то каким образом достигается утверждение "в любой звёздной системе существуют развилки." ведь по факту должны существовать оконечные вершины имеющие лишь одно ребро?

3. если рассмотреть первый пример данных из задания, то при соединении вершин 1 и 3 мы получим для любой из следующих пар ([1,2] [1,3] [1,4] [2,3] [2,4]) по два возможных маршрута (правда отличающихся длинной), что противоречит условию "Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети." и п.п 1.4 и 1.4?

Подскажите пожалуйста, что именно я понимаю неверно.

[Wataru]

1.1 Да

1.2 Да

1.3 Да

1.4 Да. Граф - дерево. Существование маршрута говорит, что в графе одна компонента связности. В ней n вершин и n-1 ребро. Это 100% дерево.

2.1 Да

2.2 Это косяк составителей. Они, видимо, хотели ввести эти самые развилки. Но вместо в "некоторых" системах написали в "любых".

3 Нигде не сказано, что это свойство должно сохраниться после добавления новой магистрали. Более того, оно 100% всегда нарушится. Если в дерево добавить ребро, то оно всегда образует цикл. Также нарушится другое свойство - магистралей теперь будет не n-1, а ровно n. Но это же у вас не вызывает вопросов?

[Роман]

Илья Николаевский, спасибо.

Но это же у вас не вызывает вопросов?

Нет, если 2.2 и 3 подразумевает нарушение озвученных правил, то остальные нарушения подразумеваются сами собой, а я интересовался только с практической точки зрения, просто люблю решать головоломные (не типичные для меня) задачки

[Роман]

Илья Николаевский, получается, что для решения задачи надо связать 2 несвязанные ребром вершины, выбранные таким образом, чтобы сумма ребер, входящих в эти вершины была максимальной из всех возможных комбинаций?

[Wataru]

Роман, Да, именно - надо найти две несвязанные вершины с максимальной суммой степеней.

[Роман]

Илья Николаевский, спасибо, спрашивал потому, что в вашем ответе немного недопонимал терминологию (например что имелось ввиду под степенями, и почему использован именно данный термин). Теперь уже все понятно. Но остался вопрос по второму, предложенному вами варианту:

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

По моему данный алгоритм будет не верен для следующей ситуации:

[Роман]

Илья Николаевский, извиняюсь, в ПЯТЫЙ раз не правильно считаю (но суть осталась та же)))

5*(5-1)/2 + 5*(5-1)/2 < 9*(9-1)/2 + 2*(2-1)/2
10+10 < 36+1
20 < 37

[Wataru]

Роман,
Вы неправильно считаете. Если уж вы d(d-1)/2 суммируете, то это надо делать по ВСЕМ вершинам. В одном случае будет 5*4/2+5*4/2+8*7/2+1*0/2, а в другом 4*3/2+4*3/2+9*8/2+2*1/2. Но можно просто суммировать сами степени двух выбранных вершин. Потому что новых, добавленных развилок будет ровно столько (новая магистраль свяжется со всеми уже имеющемся в обеих вершинах). Поэтому в этом графе 8+1 - лучший вариант (9 новых развилок). Альтернатива 4+4 добавила бы только 8.

На вашей картинке ровно одна вершина с максимальной степенью (равной 8). Когда я говорил, если максимальных вершин несколько, я имел ввиду вершин со степенью, равной максимальной.

Ваш граф - случай с одной максимальной вершиной. Тут вы должны к этой восьмерке взять самую большую вершину из оставшихся, не связанную с ней. Но там остаются только листы со степенью 1. Это 8+1 новых развилок. Это лучший вариант в графе. Но если бы соседние вершины имели степени не 4 а 5, то тут сработал бы последний случай: Надо выбрать 2 максимальные вершины из соседей к этой восьмерке. Это и будут 5+5.

[Роман]

Илья Николаевский, так я же и говорю что 9+1 лучше, а по процитированному варианту

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

будет выбран вариант 4+4.
Или я что то не верно понимаю?

[Роман]

Илья Николаевский, все, разобрался

На вашей картинке ровно одна вершина с максимальной степенью (равной 8). Когда я говорил, если максимальных вершин несколько, я имел ввиду вершин со степенью, равной максимальной.

с такой поправкой да, будет правильно работать.

[Wataru]

Роман,

будет выбран вариант 4+4.

Еще раз. Какая максимальная степень в графе? 8. Одна центральная вершина.

Найдите все вершины с максимальной степенью.

Тут вы должны найти, что она такая одна. вершины 4+4 имеют степень 4, что меньше 8, поэтому они не являются вершинами с максимальной степенью. Если бы центральная вершина тоже имела степень 4, то их было бы 3.

[Роман]

Илья Николаевский, комментарием выше отписался уже по данному моменту)

Answer 2

[dalbio]

У задачи ограничение 2*10^5,так что этот вариант не подходит (сама задача:https://acmp.ru/asp/do/index.asp?main=task&id_cour...),мб я как-то не так понял условие