本文共 1384 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要计算现有的道路连接形成了多少个连通块，然后用连通块数减一得到需要修的最少道路数目。我们可以使用并查集（Union-Find）数据结构来高效地管理和合并不同的连通块。

方法思路

解决代码

import sysclass UnionFind:    def __init__(self, size):        self.parent = list(range(size + 1))  # 城镇编号从1开始    def find(self, x):        if self.parent[x] != x:            self.parent[x] = self.find(self.parent[x])        return self.parent[x]    def union(self, x, y):        x_root = self.find(x)        y_root = self.find(y)        if x_root != y_root:            self.parent[x_root] = y_rootdef main():    input = sys.stdin.read().split()    ptr = 0    while ptr < len(input):        n = int(input[ptr])        ptr += 1        if n == 0:            break        m = int(input[ptr])        ptr += 1        uf = UnionFind(n)        for _ in range(m):            a = int(input[ptr])            ptr += 1            b = int(input[ptr])            ptr += 1            uf.union(a, b)        # 统计连通块数目        roots = set()        for i in range(1, n + 1):            roots.add(uf.find(i))        count = len(roots)        print(count - 1)if __name__ == "__main__":    main()

代码解释