mansisinha16's blog

Difference in running time of recursive dfs and iterative dfs
By mansisinha16, history, 4 years ago, In English

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://codeforces.com/contest/771/problem/A

iterative solution: https://codeforces.com/contest/771/submission/87812642

recursive solution: https://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 :)

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mansisinha16 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mansisinha16 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it 
    while (!stack.empty())
    {
 
        s = stack.top();
        stack.pop();
 
        if (!visited[s])
        {
            //cout << s << " ";
            c2++;
            count+=mp[s].size();
            visited[s] = true;
        }
         for(int i=0;i<mp[s].size();i++)
         {
           if (!visited[mp[s][i]])
               stack.push(mp[s][i]);
         }
 
    }

This is not how you code an iterative dfs. The inner for loop should be inside the if !visited statement.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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://codeforces.com/contest/771/submission/87935790

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much! I did not know using map would create such a huge difference.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Map uses log(N) where as vector is O(1) if we don't use push_back operation.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply