Graph dfs-related code passes almost all test cases, fails on a few

Question

I have a following problem and corresponding code:

You have a rectangular field of size NxM. You have K marked cells. N,M,K and marked cells coordinates are read from an input file. Two marked cells are considered adjacent if they share a side. The task is to compute the number of connected components and write it to an output file.

The following code passes almost all test cases and runs on all cases I came up with on repl.it, but gives runtime-error in the automated checking system. I can't really access what the error is.

with open("input.txt") as f:
    inp = f.readlines()

line1 = list(map(int, inp[0].strip().split()))
N = line1[0]
M = line1[1]
K = line1[2]

#represent marked cells as a dictionary, key = cells, value = list of marked neighbors
dict_ = {tuple(map(int, x.strip().split())): [] for x in inp[1:]}

#collect neighbors
def get_neighbors(idx):
    i = idx[0]
    j = idx[1]
    ans = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
    return ans

#add them to the graph
def add_neighbors(idx):
    neighbors = get_neighbors(idx)
    dict_[idx] = [x for x in neighbors if x in dict_.keys()]  # return(None)


def dfs_recursive(graph, vertex, visited, path):
    visited[vertex] = True
    path.append(vertex)
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            path = dfs_recursive(graph, neighbor, visited, path)
    return path


def conn_comps(graph):
    visited = {vertex: False for vertex in graph}
    comps = []
    for vertex in graph:
        if not visited[vertex]:
            path = []
            v_path = dfs_recursive(graph, vertex, visited, path)
            comps.append(v_path)

    return comps

#populate neighbors
for idx in dict_.keys():
    add_neighbors(idx)

ans = len(conn_comps(dict_))


FOUT = open("output.txt", "w")
FOUT.write(str(ans))
FOUT.close()

My only guess is the problem with dict size - K can be as high as 10^5 by definition, N,M up to 10^5 as well. Can someone comment and suggest other improvements? This a practice problem from an old intro-level contest.

Answer 1

In case someone finds this - you just hit python's default recursion limit of 1000. Need to either rewrite iteratively or increase it manually sys.setrecursionlimit. Alas.