hackerbaba's blog

2 color graph problem. Why dfs and not bfs ?
By hackerbaba, history, 5 years ago, In English

Hello again. Just understood graphs. in this, the author gave a solution of dfs.

I was wondering, as to couldn't it be solved with Breadth First Search? Marking each level as one colour, and the other level as the second colour?

I gave a solution with BFS, but it's giving a wrong output.

Could you please help me out?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Why not? Here's a pretty simple BFS solution. https://www.hackerearth.com/submission/41568014/

Edit :I think it might be because the graph is not necessarily connected.

→ Reply