Нахождение максимального количества узлов сильно связаны, учитывая количество узлов и ребер

"Учитывая количество узлов и количество ребер, соединяющих эти узлы, расположите эти ребра так, чтобы максимальное количество узлов было сильно связано. Верните количество узлов, которые могут быть сильно связаны".

Мне интересно, есть ли формула для этого? если нет, то как я могу решить эту проблему? любая помощь будет оценена!

Источник

1 ответ

  • Если ребра ненаправленные, то ответ прост:

    мин(number of nodes, number of edges + 1)

    Это потому, что вы должны расположить узлы и ребра для формирования графа дерева.

  • Если ребра направлены, то ответ прост:

    мин(number of nodes, number of edges)

    Это потому, что вы должны расположить график по прямой линии и соединить последний узел с первым, образуя форму круга.

Источник
Другие вопросы по тегам