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

Question

我正试图在 Hackerrank 中解决这个 graph problem，这是我目前所拥有的。我正在使用 Python 字典来表示图形，并让我的 DFS 函数 return 它遍历的连接组件的长度。我的代码通过了第一个测试用例，但给了我一些其他测试用例的运行时错误。这是一个优化问题吗？如果是这样，我应该尝试优化代码的哪一部分？还是我应该尝试完全不同的方法？

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. You can overcome this issue by using a non-recursive approach such as BFS, iterative DFS or 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)}

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

Runtime error when trying to find components in a graph

python

algorithm

optimization

graph-theory

depth-first-search