时间戳

首页 > 解决方案 > 图表 dfs 相关代码几乎通过了所有测试用例，少数失败

python - 图表 dfs 相关代码几乎通过了所有测试用例，少数失败

问题描述

我有以下问题和相应的代码：

您有一个大小为 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。有人可以评论并建议其他改进吗？这是一个旧的入门级比赛的练习题。

标签： pythondictionarymemory-managementruntime-errordepth-first-search

解决方案

万一有人发现 - 你只需达到 python 的默认递归限制 1000。需要迭代地重写或手动增加它sys.setrecursionlimit。唉。

推荐阅读