Discussion @ 1069. Prufer Code @ Timus Online Judge

O(n) wefgef 4 Jun 2006 18:45

has anyone done it in O(n)?

Re: O(n) Cybernetics Team 5 Jun 2006 16:13

yes

Re: O(n) ASK 19 Feb 2010 03:22

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

Edited by author 19.02.2010 03:23

Re: O(n) Sofigenr 13 Mar 2010 20:55

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.

Re: O(n) and Idea Felix_Mate 28 Aug 2015 00:23

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

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

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

Edited by author 28.08.2015 00:24

Re: O(n) and Idea c_pp 14 Dec 2016 02:25

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)) :)

Re: O(n) and Idea c_pp 14 Dec 2016 11:32

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

Re: O(n) and Idea index 12 Feb 2017 15:50

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

Discussion of Problem 1069. Prufer Code