Question link-https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/water-flow-4-38cea6c6/?layout=old
My Code Link-https://ide.codingblocks.com/s/328670
Getting wrong answer
My logic is to run dfs on each city and inside dfs I am going only to those cities which are not blocked.
Water Supply Hackerearth
You can also go to cities which are blocked. But you can’t pass through those cities.
This is my code for the same question. It gives TLE in one case. Please check it and tell me if you are able to understand it.
I understood your code but Why are we getting TLE
DFS is an O(n) algorithm and because of the outer loop, overall time complexity becomes O(n^2) which gives TLE. I suggest you to check the editorial of this question as well.
They also used dfs but they are not calling dfs on each node.
I got AC
Oh okay cool. You can mark your doubt as resolved now.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.