链接: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);
}
//最少建设的道路数量 ->村中心数 - 1
int min_roads = unionFind.sets() - 1;
System.out.println(min_roads);
}
}
}
}
class UnionFind {
HashMapvillage;
//集合数 -- 多少个村中心
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;
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧