My logic is giving WA on 50% of the test cases. I am not able to figure out what is wrong with my logic. Any help would be great.
Logic: I apply a regular dfs, and return true or false. True indicates, that it is indeed the shortest the path, while false indicates, that it is not. If we get a true, then we update the parent node, else we don't.
Code: Code
UPDATE: Solved using DP but would be curious to know, if anyone can do it without DP.
The graph in question is directed where as in your code you are making it undirected.