Erreur d'exécution lorsque vous essayez de trouver des composants dans un graphique

Question

J'essaie de résoudre ce graph problem dans Hackerrank et c'est ce que j'ai jusqu'à présent. J'utilise un dictionnaire Python pour représenter le graphe et faire en sorte que ma fonction DFS renvoie la longueur du composant connecté qu'il traverse. Mon code passe le premier cas de test mais me donne une erreur d'exécution pour certains autres cas de test. Est-ce un problème d'optimisation? Si oui, quelle partie de mon code devrais-je essayer d'optimiser? Ou devrais-je essayer une approche différente?

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

Depuis qu'il pourrait y avoir 2 * 15000 nœuds, vous êtes probablement exceeding maximum recursion depth. Vous pouvez résoudre ce problème en utilisant une approche non récursive, telle que BFS, itérative DFS ou disjoint-set data structure.

Une autre façon est d'augmenter la limite de récursion:

sys.setrecursionlimit(30000) 

Aussi la question utilise l'indexation de base 1 de sorte que vous devez modifier cette ligne:

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

à

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