试图在图中查找组件时出现运行时错误
问题描述:
我正在尝试在Hackerrank中解决这个graph problem,这是迄今为止我所知道的。我正在使用Python字典来表示图形,并让我的DFS函数返回它所遍历的连接组件的长度。我的代码通过了第一个测试用例,但给我一些其他测试用例的运行时错误。这是一个优化问题吗?如果是这样,我应该尝试优化哪部分代码?或者我应该尝试完全不同的方法?试图在图中查找组件时出现运行时错误
import sys
n = input()
# Graph
g = {k:set() for k in xrange(2*n)}
# DFS stuff
visited = set()
def dfs(g,s,S=set(),dfs_sum=0):
S.add(s)
dfs_sum +=1
for i in g[s]:
if i in S: continue
dfs_sum = dfs(g,i,S,dfs_sum)
return dfs_sum
# Building the graph
for i in xrange(n):
a,b = map(int,raw_input().split())
g[a].add(b)
g[b].add(a)
# Getting the max and min lengths of the connected components
max_len, min_len = 0, sys.maxint
for i in xrange(n):
if i not in visited:
v = dfs(g,i,visited)
if v > 1: # Ignore single nodes
max_len, min_len = max(max_len, v), min(min_len, v)
print("{} {}".format(min_len,max_len))
答
因为有可能是2 * 15000个节点,你可能exceeding maximum recursion depth。您可以通过使用非递归方法(如BFS,迭代DFS或disjoint-set data structure)来解决此问题。
另一种方法是增加递归限制:
sys.setrecursionlimit(30000)
另外的问题是使用基于1的索引,所以你应该改变这一行:
g = {k:set() for k in xrange(2*n)}
到
g = {k:set() for k in xrange(2*n+1)}
谢谢!原来这是两个!一些运行时错误是KeyErrors,因为由于我的索引不正确,图形没有正确构建。我像你说的那样设置了递归限制,并将图改为'g = {k:set()for k in xrange(1,2 * n + 1)}',它效果很好。另外,我将最后一个循环范围从'range(n)'更改为'range(1,n + 1)' – spidertothefly127