У меня была идея убить вершину с самой большой степенью.А потом из каждой компоненты связности пускать дфс и делать из неё цепь.Потом добавить к ответу кол-во самих компонент(тоесть рёбра, которые нужно будет построить чтобы соединить сами полученые цепи).Как оказалось-идея или реализация была не правильной.
76 2010-03-08 20:35:13
Re: Постройка цикла Гамильтона на дереве. (4 ответов, оставленных в Problems)
77 2010-03-07 22:55:33
Тема: Постройка цикла Гамильтона на дереве. (4 ответов, оставленных в Problems)
Дано дерево с 3<=N<=100000 вершинами.Какое минимальное количество рёбер нужно построить чтобы получился цикл Гамильтона?