Hi,
I have just started with learning graphs and was doing a question which involved basic dfs. While doing it, I was getting TLE when I was using iterative dfs and when I only changed the dfs from iterative to recursive, the solution got accepted. Since the time complexity of both the methods are same, the only reason I could think of is the time taken to push and pop in the stack, but I didn't think the difference would be this huge.
These are the links:
Problem: https://mirror.codeforces.com/contest/771/problem/A
iterative solution: https://mirror.codeforces.com/contest/771/submission/87812642
recursive solution: https://mirror.codeforces.com/contest/771/submission/87812583
I am baffled by the difference in the runtime of the 2 solutions. If anyone knows a reason for this, please help me :)
Auto comment: topic has been updated by mansisinha16 (previous revision, new revision, compare).
Auto comment: topic has been updated by mansisinha16 (previous revision, new revision, compare).
This is not how you code an iterative dfs. The inner for loop should be inside the if
!visitedstatement.Thank you so much! I now realise that it is doing extra iterations even for visited nodes in my code. I'll keep this is mind :)
Hi Another reason why you are getting TLE is that are you using maps instead of vectors for storing the adjacency list. I just changed your code to store the list using vectors instead of maps and it got AC. Here is the link to the submission: https://mirror.codeforces.com/contest/771/submission/87935790
Thank you so much! I did not know using map would create such a huge difference.
Map uses log(N) where as vector is O(1) if we don't use push_back operation.
but hashmap gives tle as well , even though it also inserts in O(1). Though there must be difference in time of insert in hashmap and push_back in vector.