TLE in Fire Escape Route

Problem Link: https://www.codechef.com/problems/FIRESC

Below is my code can anyone tell me what is wrong with my code, It is giving TLE even I implemented the iterative approach of DFS, even the recursive approaches passes all the test case.

Thanks in Advance :slight_smile:
@waqar_ahmad224 @ssjgz @ssrivastava990 @aneee004 @hello_hell @galencolin

from sys import stdin 

mod=10*9 +7 
def inp():
    return int(stdin.readline())

def mp():
    return map(int,stdin.readline().split())


def DFS(d,ver,visited,ans):
    visited.add(ver)
    c=1
    stack=[ver]
    while stack:
        flag=0
        for i in d[stack[-1]]:
            if i not in visited:
                flag=1
                visited.add(i)
                stack.append(i)
                c+=1
                break
        if not flag:
            stack.pop()
    

    ans=(ans%mod * c%mod)%mod
    return ans

def solve():
    n,m=mp()
    d={i:set() for i in range(1,n+1)}
    for i in range(m):
        a,b=mp()
        d[a].add(b)
        d[b].add(a)

    c,ans=0,1
    visited=set()

    for i in range(1,n+1):
        if i not in visited:
            c+=1
            ans=DFS(d,i,visited,ans)

    print(c,ans)

for _ in range(inp()):
    solve()

First of all, your constant factor is going to be horrible, what with you using sets to keep track of visited vertices and adjacency lists. But the real issue is that it’s O(n^2): think about what happens when, for each neighbor of a vertex, you break and reset a loop that visits every neighbor.

2 Likes

Can you guide me to how to optimize it ?
I used set because of its searching time complexity(O(1)) because we need to check if we already visited the node.

Sets have O(\log n) search complexity, unless you’re using hash sets. An easier and efficient alternative is a list. vis[i] will be 0 if i is not visited, and 1 if visited.

3 Likes

python sets are by default hashsets, and there’s actually no C++ style set in the library, which is incredibly annoying

4 Likes

Sure, But in this article it is written that sets have O(1) average time and O(n) worst time complexity.
Can you provide me the source of O(log n ) complexity in sets?
Thanks :slight_smile:

My bad. I didn’t know Python implements only Hash sets. A tree set will be O(\log n). Which I believe you can only have in C++/Java

Anyhow, it’s better use a list, which promises O(1) lookup.

3 Likes

Sorry to bother you, can you now tell me where i have to improve my code https://www.codechef.com/viewsolution/36184517

PS:I’m learning graphs that’s why so much doubts
Thanks

1 Like

Why do you break here?

Check this for an iterative implementation of DFS.

Additional Tip: Mark the node visited as soon as you push it into your stack.

3 Likes

I know the recursive approach better but we all know python is slow so I want the iterative solution of this recursive approach and I find this.
From here I saw the iterative code.

This is some random library that makes no guarantees about complexity, you shouldn’t always trust things on the internet (hint hint: geeksforgeeks)

4 Likes

Thanks for testing my code, do you find any bug?
I tried using list too https://www.codechef.com/viewsolution/36184517

Read the whole of my comment above, the part about it being O(n^2) has nothing to do with sets. @aneee004’s comment tells you how to fix it, I think all you need to do is get rid of the break statement.

3 Likes

Have u solved this problem or still u have doubt ?

Try this -

def DFS(d,ver,visited,ans):
    stack=[ver]
    c=1
    visited[ver]=True
    while stack:
        s=stack.pop()
        for i in d[s]:
            if not visited[i]:
                c+=1
                visited[i]=True
                stack.append(i)
    ans=(ans%mod * c%mod)%mod
    return ans

I hope it will work.

1 Like

And that’s how you write an iterative DFS. For a BFS, replace the stack with a queue. (In Python that means pop(0) I believe).

Python pop function pops the value from last .

pop(0) would do from first

2 Likes

Oh sry , Basically if u use pop(i) then it will pop the i’th element (i<n) , while simple pop function pop the last element .

Yeah. Pop default parameter is probably -1.

1 Like