本文共 1524 字，大约阅读时间需要 5 分钟。
为了解决这个问题，我们需要计算在每个可能被占领的城市被移除后，剩下的城市连通所需修建的公路数量。通过分析连通分量的数目，我们可以得出需要修建的公路数量。
import sysfrom collections import dequedef main(): # 读取输入 n, m, k = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(n + 1)] for _ in range(m): u, v = map(int, sys.stdin.readline().split()) graph[u].append(v) graph[v].append(u) cities_to_check = list(map(int, sys.stdin.readline().split())) # 处理每个被检查的城市 for c in cities_to_check: visited = [False] * (n + 1) cnt = 0 for j in range(1, n + 1): if j == c: continue if not visited[j]: cnt += 1 queue = deque() queue.append(j) visited[j] = True while queue: u = queue.popleft() for v in graph[u]: if v != c and not visited[v]: visited[v] = True queue.append(v) print(cnt - 1)if __name__ == "__main__": main()
sys.stdin.readline读取输入数据，避免输入速度慢的问题。读取城市数目N，公路数目M，以及被检查的城市数目K。graph存储图的结构，每个城市对应一个列表，存储其相邻城市。c，初始化一个visited数组，标记访问状态。使用BFS遍历剩下的城市，计算连通分量数目。通过这种方法，我们可以高效地解决问题，确保在合理的时间内完成计算。
转载地址：http://dctuz.baihongyu.com/