Python最长广播响应

摘要：from collections import dequedef compute_response_time(N, links, start_node):# 构建邻接表adj = [ for _ in range(N + 1)]for u, v in link

from collections import dequedef compute_response_time(N, links, start_node):# 构建邻接表adj = [ for _ in range(N + 1)]for u, v in links:adj[u].append(v)adj[v].append(u)# BFS初始化distance = [-1] * (N + 1)distance[start_node] = 0queue = deque([start_node])# 执行BFSwhile queue:current = queue.popleftfor neighbor in adj[current]:if distance[neighbor] == -1:distance[neighbor] = distance[current] + 1queue.append(neighbor)# 找出最远距离max_distance = max(distance[1:N + 1])return max_distance * 2# 读取输入N, T = map(int, input.split)links = for _ in range(T):u, v = map(int, input.split)links.append((u, v))start_node = int(input)# 计算并输出结果print(compute_response_time(N, links, start_node))构建图的邻接表：使用给定的连接关系，构建一个无向图的邻接表表示。广度优先搜索（BFS）：从广播结点出发，使用BFS计算到所有其他结点的最短距离。因为消息传递是双向的，且响应时间等于发送时间的往返，所以总时间为到达最远结点距离的两倍。确定最大距离：在BFS完成后，找出所有结点中最远的那个距离，乘以2即为所需的最短等待时间。