DFS陷入无限循环求助：数组邻接填充计数的DFS实现修复

你的DFS陷入无限循环的核心原因是没有标记已访问的位置：当递归到spot后，会继续递归spot-1，而spot-1的DFS又会回头递归spot，此时district[spot]仍然为1，导致无限往复调用。

下面提供两种可行的修复方案：

方案一：使用访问集合记录已处理位置 #

通过额外的visited集合跟踪已经遍历过的位置，避免重复递归：

def solution(queries):
    length = max(queries) + 1
    district = [0] * length

    def dfs(spot, district, visited):
        # 越界、未标记、已访问过的位置直接返回0
        if spot < 0 or spot >= len(district) or district[spot] == 0 or spot in visited:
            return 0
        visited.add(spot)
        # 递归统计左右相邻区域
        return 1 + dfs(spot-1, district, visited) + dfs(spot+1, district, visited)
    
    res = []
    for q in queries:
        district[q] = 1
        # 每次计算新创建一个空的访问集合
        curr = dfs(q, district, set())
        res.append(curr)
    return res

方案二：临时修改标记再恢复 #

通过临时将当前访问的位置设为0（标记为已访问），递归完成后再恢复为1，既避免循环又不破坏原数组的状态：

def solution(queries):
    length = max(queries) + 1
    district = [0] * length

    def dfs(spot, district):
        if spot < 0 or spot >= len(district) or district[spot] == 0:
            return 0
        # 临时标记为已访问（设为0）
        district[spot] = 0
        # 统计当前位置+左右连通区域
        count = 1 + dfs(spot-1, district) + dfs(spot+1, district)
        # 恢复原标记
        district[spot] = 1
        return count
    
    res = []
    for q in queries:
        district[q] = 1
        curr = dfs(q, district)
        res.append(curr)
    return res

两种方案都能解决无限循环问题，且符合你提供的示例输出要求。

内容的提问来源于stack exchange，提问作者Dominic