praveenojha33's blog

By praveenojha33, history, 4 months ago, In English,

I was solving problem in which I was using simple BFS but I took MLE on test 57, but when I changed the way of marking visited node slightly it got accepted. Can anyone help me to understand the reason for this ?

This approach was Accepted.

This approach gave MLE

The only difference is in the way how I mark visited node.

Thank You !!

Tags bfs, mle
  • Vote: I like it
  • 0
  • Vote: I do not like it

4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You marked visited node when you already pop it, but in this moment there may be several more in queue(in additional you dont check if you already pop this node) and your code pop this node again. But in Accepted submission you marked node after first pushing and there can be only one node in queue

You may add if(vis[u.F]) continue; when poping