使用深度优先搜索（ DFSDFSDFS ）遍历城镇，标记连通的城镇。 对每个未被标记的城镇进行 DFSDFSDFS ，每次 DFSDFSDFS 完成表示找到一个新的连通分量。 统计连通分量的个数，并输出连通分量个数减 111 ，即最少需要建设的道路数目。因为每个连通分量之间只需要一条道路。

Rt，用并查集维护点的连通性即可。并查集时间复杂度优秀，常数小，十分适合本题。