Как найти MST графика в | V | Время дано остовное дерево плюс еще один край

Question

Мне интересно, как go решить эту проблему.

Мне дан график G = (V,E). Это связный неориентированный взвешенный граф. Граф состоит из остовного дерева и одного дополнительного ребра. Как бы я придумал алгоритм, который вычислял бы MST графика за n = |V| сложность времени. Я думал об алгоритме Крускала, но он не отвечал требованию временной сложности.

Answer 1

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