Код Graph, связанный с dfs, проходит почти все тестовые случаи, не работает в некоторых [closed]

У меня следующая проблема и соответствующий код:

У вас есть прямоугольное поле размером NxM. У вас есть отмеченные K клеток. Координаты N, M, K и отмеченных ячеек считываются из входного файла. Две отмеченные клетки считаются смежными, если у них общая сторона. Задача состоит в том, чтобы вычислить количество подключенных компонентов и записать его в выходной файл.

Следующий код проходит почти все тестовые примеры и работает во всех случаях, которые я придумал на repl.it, но выдает ошибку времени выполнения в системе автоматической проверки.

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()

Я только предполагаю, что проблема с размером дикта — K может достигать 105 по определению, Н, М до 105 тоже. Может ли кто-нибудь прокомментировать и предложить другие улучшения? Это практическая задача из старого конкурса начального уровня.