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.
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.
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.
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
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.
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.
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