Discussion @ 1416. Confidential @ Timus Online Judge

Is O(N^2) the fastest solution ?

Posted by N.M.Hieu ( DHSP ) 14 May 2006 20:21

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 ?

Posted by N.M.Hieu ( DHSP ) 14 May 2006 22:20

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 ?

Posted by Ludovic 9 Sep 2006 07:51

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)

Discussion of Problem 1416. Confidential