链接：https://www.luogu.com.cn/problem/P1536

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

代码：

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {//村庄数int num = sc.nextInt();if(num != 0) {UnionFind unionFind = new UnionFind(num);//路的数量int roads = sc.nextInt();for (int i = 0; i < roads; i++) {int x = sc.nextInt();int y = sc.nextInt();unionFind.union(x, y);}//最少建设的道路数量 -> 村中心数 - 1int min_roads = unionFind.sets() - 1;System.out.println(min_roads);}}}
}class UnionFind {HashMap<Integer, Integer> village;//集合数 -- 多少个村中心private int sets;public UnionFind(int n) {//初始化，视 每个村庄都是独立的（村中心）sets = n;village = new HashMap<>();for (int i = 1; i < n; i++) {village.put(i, null);}}public int findVillageCenter(int x) {int center = x;//找 村中心while (village.get(center) != null) {center = village.get(center);}//压缩路径 -- 登记村庄的村中心while (village.get(x) != null) {int old = village.get(x);village.put(x, center);x = old;}return center;}//将两个村中心 连通public void union(int x, int y) {int centerX = findVillageCenter(x);int centerY = findVillageCenter(y);if (centerX != centerY) {sets--;village.put(centerX, centerY);}}//返回村中心的数量public int sets() {return sets;}
}