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

Question

我正在尝试解决 Hackerrank 中的这个图问题，这就是我到目前为止所拥有的。我使用 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 个节点，因此您可能超过最大递归深度。您可以通过使用非递归方法（例如 BFS、迭代 DFS 或不相交集数据结构）来克服此问题。

另一种方法是增加递归限制：

sys.setrecursionlimit(30000)

问题还在于使用基于 1 的索引，因此您应该更改此行：

g = {k:set() for k in xrange(2*n)}

到

g = {k:set() for k in xrange(2*n+1)}

Answer 2

非常感谢。我通过了一个 USACO 问题，这太疯狂了> 递归限制> 显然，c++ 默认有这个。没办法