I am using Prim's algorithm but gives TLE!

#1

According to me, Prims algo should take ElogV time and that is under the constraints but still I get TLE!

#2

My code : https://ide.codingblocks.com/s/179072

#3

Hey @ayushjain.iitg
Your code is N^2 because in your findMinVertex function you’re doing linear traversal. Your findMinVertex should be logn.


See this for better understanding.

#4

If your doubt is resolved please mark doubt as cleared. Thanks and best of luck !!

#5

Please share with me the code of O(ElogV) which uses the coding style as taught in videos to us. The way graph is created and implemented on gfg is too different from our practice. I hope you can quickly implement it and share with me the code id!!!
Thanks

#6


This has the logn optimisation for your code. Take idea from it and try again. Best of luck !!.
And if your doubt is clear please mark it as closed.

1 Like
#7

That’s awesome @Aarnav-Jindal-1059677350830863. I’ll try it again !

1 Like
#8

That gave me AC in one go!!
Thanks a lot for the idea and one thing I need to ask is that while reading from gfg, I got to know they are using min heaps to get it in logn. You used set because set is based on min heap??!

#9

No set and heap are different. Both work fine conceptually for our problem. But you’ll see that while we used STL set, for heap we need to make a custom one which is time consuming. That is why I used set.
Hope that helps and if your doubt is cleared, please mark it as closed.

1 Like