Блог пользователя mansisinha16

Difference in running time of recursive dfs and iterative dfs
Автор mansisinha16, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится 
    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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить