Jun 2016
1 / 3
Jun 2016
Jun 2022
bhavik29
Jun '16

My program is working perfectly with all the test cases. Yet, when I submit the solution it gives NZEC - runtime error.
http://www.spoj.com/problems/BUGLIFE/20

def dfs(graph, start, visited = None, parent = None):
	if visited == None:
		visited = set()
		visited.add(start)
	for num in graph[start]:
		if num not in visited:
			visited.add(num)
			if dfs(graph,num,visited,start):
				return True
		else:
			if num != parent:
				return True
	return False
tc = int(raw_input())
for i in range(1, tc+1):
	yo = {}
	s = raw_input()
	n, r = map(int, s.split())
	for j in range(r):
		s = raw_input()
		p, q = map(int, s.split())
		yo[p] = yo.get(p,[]) + [q]
		yo[q] = yo.get(q,[]) + [p]
	start = q
	if dfs(yo, start):
		print "Scenario #%d:" %(i)
		print "Suspicious bugs found!"
	else:
		print "Scenario #%d:" %(i)
		print "No suspicious bugs found!"

  • created

    Jun '16

  • last reply

    Jun '22
  • 2

    replies

  • 1.3k

    views

  • 3

    users

  • 1

    like

  • 1

    link

daft_wullie
Jun '16

At SPOJ you have to be careful using recursive algorithms in Python. Be aware that the recursion limit is quite low (approx. 1000) and that recursion is not very fast in Python. So you have to be sure that your recursive algorithm terminates quickly, which is fine for e.g. Divide & Conquer algos. But your DFS is called again and again with only one node more visited. And there can be lots of interactions / nodes.So you probably should do a iterative DFS instead of recursive. Furthermore I think your algorithm is not correct, because it considers this case as 'suspicious' 

1
2 2
1 2
2 1

.

6 years later
neel0086
Jun '22
2

So in python to avoid nzec add this 2 lines above

import sys
sys.setrecursionlimit(10**4)