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

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.

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 105 by definition, N,M up to 105 as well. Can someone comment and suggest other improvements? This a practice problem from an old intro-level contest.