求解无向图顶点停止消失时长及代码KeyError问题排查

KeyError:4说明你的代码在尝试访问编号为4的顶点，但测试用例里N=4，顶点编号范围是0到3，根本不存在顶点4。多半是初始化数据结构（比如度数数组、邻接表）时不小心包含了超出0~N-1范围的顶点，或者遍历逻辑里错误生成了顶点4的引用。

常见的出错情况：

• 初始化度数数组时写成了degree = [0]*(N+1)，导致数组长度为5（索引0到4），后续逻辑误碰了degree[4]；
• 邻接表用字典实现时，错误添加了键为4的条目；
• 循环遍历顶点时用了range(N+1)而非range(N)，遍历到了不存在的顶点4。

修正方案 #

1. 所有数据结构严格只针对0~N-1的顶点：

   • 度数数组长度设为N，索引对应顶点编号0到N-1；
   • 邻接表只包含0到N-1的顶点；
   • 遍历顶点时用range(N)。

2. 用拓扑排序（BFS）的思路实现逻辑，这是处理这类逐层删节点问题的标准方法，能有效避免越界访问：

def calculate_disappearing_time(N, A, B):
    from collections import deque

    # 初始化邻接表和度数数组，严格对应0~N-1的顶点
    adj = [[] for _ in range(N)]
    degree = [0] * N

    # 构建无向图的邻接表和度数统计
    for a, b in zip(A, B):
        adj[a].append(b)
        adj[b].append(a)
        degree[a] += 1
        degree[b] += 1

    # 初始化队列：把所有初始度数<=1的顶点放进去，标记它们的消失时间为1
    q = deque()
    time = [0] * N  # 0表示该顶点不会消失
    for i in range(N):
        if degree[i] <= 1:
            q.append(i)
            time[i] = 1

    # 逐层处理顶点消失
    while q:
        current = q.popleft()
        # 遍历当前顶点的所有邻居
        for neighbor in adj[current]:
            if time[neighbor] == 0:  # 只处理还没消失的邻居
                degree[neighbor] -= 1
                # 如果邻居度数降到<=1，标记消失时间并加入队列
                if degree[neighbor] <= 1:
                    time[neighbor] = time[current] + 1
                    q.append(neighbor)

    # 最大的消失时间就是答案，没有顶点消失则返回0
    return max(time) if max(time) != 0 else 0

# 测试用例1：预期输出2
print(calculate_disappearing_time(7, [0,1,2,1,4,4], [1,2,0,4,5,6]))

# 测试用例2：环结构，预期输出0，无KeyError
print(calculate_disappearing_time(4, [0,1,2,3], [1,2,3,0]))

代码说明 #

• 用列表列表实现邻接表，避免字典的键不存在问题；
• 度数数组严格对应每个顶点的编号，不会出现越界；
• time数组记录每个顶点的消失时间，未消失的顶点时间保持0，避免重复处理；
• BFS过程中只处理未消失的邻居，不会访问已移除的节点。

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