工作时做网站使用软件,工程造价信息网官网查询,网站建设方案选择实现方式,免费云服务器推荐并查集解决案例畅通工程
案例问题介绍#xff1a;
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还…并查集解决案例畅通工程
案例问题介绍
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?在我们的测试数据文件夹中有一个trffic project.txt文件它就是诚征道路统计表下面是对数据的解释:
解题思路:
创建一个并查集UF _Tree _Weighted(20)分别调用union(0,1),union(6,9),union(3,8),union(5,11),union(2,12),union(6,10),union(4,8) ,示已经修建好的道路把对应的城市连接起来;如果城市全部连接起来,那么并查集中剩余的分组数目为1 , 所有的城市都在一个树中 ,所以,只需要获取当前并查集中剩余的数目,减去1就是还需要修建的道路数目;
数据集
traffic.txt
20
7
0 1
6 9
3 8
5 11
2 12
6 10
4 8Python功能实现及测试
from Structure.UF.UF_Tree_Weighted import UF_Tree_Weightedwith open(../traffic.txt, r) as f:total int(f.readline())uft UF_Tree_Weighted(total)connected_nums int(f.readline())# print(connected_nums)for i in range(connected_nums):road f.readline().split()uft.unite(int(road[0]), int(road[1]))# print(uft.in_the_same_group(int(road[0]), int(road[1])))print(uft.num_groups)print(uft.groups)print(fElements number in each group: {uft.nums_in_each_group})print(fTo make the provinces traffic fluent, fthe number of remanent roads should be connected is {uft.count_groups()-1})运行结果
13
[1, 1, 12, 8, 8, 11, 9, 7, 8, 9, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Elements number in each group: [0, 2, 0, 0, 0, 0, 0, 1, 3, 3, 0, 2, 2, 1, 1, 1, 1, 1, 1, 1]
To make the provinces traffic fluent, the number of remanent roads should be connected is 12只需要调用上一节实现的路径压缩优化后的并查集即可实现
