Блог

Главная - Вопросы по программированию - Код, связанный с графом dfs, проходит почти все тестовые случаи, в некоторых из них происходит сбой

Код, связанный с графом dfs, проходит почти все тестовые случаи, в некоторых из них происходит сбой

#python #dictionary #memory-management #runtime-error #depth-first-search

Вопрос:

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

У вас есть прямоугольное поле размером 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 может достигать 10^5, N,M также до 10^5. Может ли кто-нибудь прокомментировать и предложить другие улучшения? Это практическая проблема из старого конкурса начального уровня.

Комментарии:

1. можете ли вы опубликовать «input.txt»? так что будет проще запустить этот код

2. он работает со многими тестовыми случаями, и, к сожалению, у меня нет доступа к тому, на котором он выходит из строя. случай, когда это действительно работает, например,’2 2 2′ ‘1 2’ ‘2 1’ ( каждая строка в отдельной строке), с ответом 2 (два компонента)

3. можете ли вы сослаться на исходный вопрос, если позволите?

4. Оригинальная ссылка и скриншот, которые у меня есть, только на русском языке. Но то, что я опубликовал, является более или менее прямым переводом за вычетом некоторого пуха (т. Е. Они прямо не говорят, что вам нужно вычислять подключенные компоненты, но вы можете легко сделать вывод). Суть в том, что вы читаете три числа N, M, K из первой строки, а затем у вас есть K строк по два целых числа в каждой, которые являются координатами отмеченных ячеек. Помеченные ячейки считаются смежными по бокам (но не по углам).

5. хорошо, позвольте мне попробовать отладить ваш код, спасибо

Ответ №1:

В случае, если кто — то найдет это-вы просто достигнете предела рекурсии python по умолчанию в 1000. Нужно либо переписывать итеративно, либо увеличивать его вручную sys.setrecursionlimit . Увы.

Метки: , , ,