Runtime error when trying to find components in a graph

Question

I am trying to solve this graph problem in Hackerrank and this is what I have so far. I am using a Python dictionary to represent the graph and have my DFS function return the length of the connected component that it traverses. My code passes the first test case but gives me a Runtime error for some of other other test cases. Is it an optimization problem? If so, which part of my code should I try optimizing? Or should I try a different approach altogether?

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

Since there could be 2*15000 nodes, you are probably 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.

Another way is to increase the recursion limit:

sys.setrecursionlimit(30000)

Also the question is using 1-based indexing so you should change this line:

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

to

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