primov na O(n^2)!!!

evo mene opet!!
s'tim sto je sada pored onog "trika" problem i ovaj "kablovi"!
e to je tipican Primov algoritam - naravno!

nego, mene zanima da li mozete da mi potvrdite da NE postoji veca optimizacija primovog algoritma koji sam ja iskoristio u ovom zadatku ali i da postoji algoritam koji ce biti slozenosti n^2 a ne n^3 kao kod mene!
sa tim n^3 ne prolazi poslednji test!
:[

i naravno, ako postoji, gde bih mogao da nadjem (algoritam n^2)?

Primov je originalno O(n^2), kako si ti dosao do O(n^3)?

Dimitar je u pravu. Imas sa O(n^2) na O(n log(n)).

ne znam vise ni sam gde sam pronasao algoritan O(n^3)!!
znam da je bila neka knjiga (cudo jedno) pa sam, posto kod nije bio u paskalu, prekucao ali tako da mi je ispalo O^3... kod koji sam poslao za ovaj zadatak sadrzi taj "moj" Primov algoritam (ali i on radi samo za n<256 koliko skup moze da ima clanova - za ovaj zadatak ce raditi posto ima max 100 cvorova ali poslednji test nece zbog vremena)

a sad me je bas zainteresovao taj Primov algoritam O(n^2)... ne samo zbog ovog zadatka ... pa bih vam bio zahvalan ako biste me uputili na mesto gde bih mogao da ga nadjem!!!
:)

Potrazi na google "algorithm+prim". Isto za minimum spanning tree mozes da razgledas i algoritam na Kruskal.

;]