试图在图中查找组件时出现运行时错误

Question

我正在尝试在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)) 

Answer 1

因为有可能是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)}