Is O(N^2) the fastest solution ?

I think O(N^2) ( Prim + DFS )is the fastest way to solve this problem , is it right ?

Re: Is O(N^2) the fastest solution ?

Posted by

Alexey 14 May 2006 20:30

Tell me, Why Kruscal+DFS doesn't work? I have TLE#12.

Should I write Prim?

Re: Is O(N^2) the fastest solution ?

I think Kruskal + DFS is enough.

Maybe you need to optimize your code.

Nguyen Dinh Tu ( DHSP ), my fiend , has got AC with the complexity O(N^3)( 0.89s ) . He used Prim , too.

Re: Is O(N^2) the fastest solution ?

Posted by

Alexey 15 May 2006 18:14

OK, then tell me, please, how to find the second answer?

I use DFS... May be I should delete the largest vertic and

run Kruscal again?

Re: Is O(N^2) the fastest solution ?

You may try adding each non-MST edge to the MST and delete the longest MST edge in the cycle.

Re: Is O(N^2) the fastest solution ?

Posted by

-XraY- 25 Oct 2011 16:23

I don't know how, but my O(n^2) solution works 0.312 sec)