0

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))
Saeid
  • 4,147
  • 7
  • 27
  • 43
prithajnath
  • 2,000
  • 14
  • 17

1 Answers1

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)}
Community
  • 1
  • 1
Saeid
  • 4,147
  • 7
  • 27
  • 43
  • 1
    Thanks! Turns out that it was both! Some of the Runtime errors were KeyErrors because the graph wasn't being built properly due to my incorrect indexing. I set the recursion limit like you said and changed the graph to `g = {k:set() for k in xrange(1,2*n+1)}` and it worked great. Also, I changed the last for loop range from `range(n)` to `range(1,n+1)` – prithajnath Dec 27 '16 at 05:42