試圖在圖中查找組件時出現運行時錯誤

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)}