has anyone done it in O(n)?

yes

http://en.wikipedia.org/wiki/Prufer_code


Edited by author 19.02.2010 03:23

But this solution is O(n^2)
becouse of
...
 7 for each value i in a
 8     for each node j in T
...
maybe I don't understand whi it is O(n) so
I ask you tell me why please.
Sorry for bad English.

Никто с форума  не знает решение O(N), т.к. в рейтинге решений у всех время 0.015, которое соответствует N*logN (я сам так решил).

Идея задачи проста-на очередном шаге находить ещё не использованные вершинки (а также отсутствующие в оставшемся списке),и среди всех таких вершины с минимальным номером. Это как раз и будут "очередные" в "оставшемся" дереве висячие вершины.

Стандартное решение с использованием кучи работает O(N*logN). Если кто-нибудь ДЕЙСТВИТЕЛЬНО знает решение за O(N), то напишите на общем форуме.

Edited by author 28.08.2015 00:24

http://e-maxx.ru/algo/prufer_code_cayley_formula

But I'm not sure, because need to sort edges, so anyway O(n*log(n)) :)

I'm implemented O(N) algo, and got 0.001s AC!.

You can easily do it in O(N) with counting sort.