原题链接;http://acm.hdu.edu.cn/showproblem.php?pid=1232 .... http://acm.hdu.edu.cn/showproblem.php?pid=1
1232 就是 判断 有几个城市是孤立的,未连通。。用并查集可以解决这个问题。。说说并查集吧。。
l并查集:(union-find
sets)
一种简单的用途广泛的集合. 并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数等。最完美的应用当属:实现Kruskar算法求最小生成树。
l并查集的精髓(即它的三种操作,结合实现代码模板进行理解):
1、Make_Set(x)
把每一个元素初始化为一个集合
初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身(也可以根据情况而变)。
2、Find_Set(x)
查找一个元素所在的集合
查找一个元素所在的集合,其精髓是找到这个元素所在集合的祖先!这个才是并查集判断和合并的最终依据。
判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
合并两个集合,也是使一个集合的祖先成为另一个集合的祖先,具体见示意图
3、Union(x,y)
合并x,y所在的两个集合
合并两个不相交集合操作很简单:
利用Find_Set找到其中两个集合的祖先,将一个集合的祖先指向另一个集合的祖先。如图
l并查集的优化
1、Find_Set(x)时
路径压缩
寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了,如下图所示;可见,路径压缩方便了以后的查找。
2、Union(x,y)时
按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。
具体代码 就不贴啦。。网上随便一搜就有。。以上并查集参考资料链接:http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.html
再回到这个题上吧。。
代码
1233题:克鲁斯卡尔算法。。
不知道的百度 吧。。这里简单说一下实现过程。。先对所有的道路 按照 道路长短(从短到长)排序。。然后依次循环各个道路。。判断该道路的两点是否已经连通了。。如果连通执行下一次循环。否则 用sum+=该道路长度,将这两点连通(用并查集实现)。。就这样循环完 sum就是答案了。。对了,sum开始要初始化为0,别忘了。。
1233代码:
分享到:
相关推荐
离线OJ题库(HDU ZJU等,部分有答案),需联网。
OJ,数据结构,算法等的一个杂集 OJ,数据结构,算法等的一个杂集 OJ,数据结构,算法等的一个杂集 OJ,数据结构,算法等的一个杂集 OJ,数据结构,算法等的一个杂集 OJ,数据结构,算法等的一个杂集 OJ,数据结构,...
算法笔记 可供各学校计算机上机复试及各OJ平台刷题使用算法笔记 可供各学校计算机上机复试及各OJ平台刷题使用算法笔记 可供各学校计算机上机复试及各OJ平台刷题使用算法笔记 可供各学校计算机上机复试及各OJ平台刷题...
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于...
C++实现oj算法代码---贪心算法
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
XMU OJ 1230的解题报告和源代码 菜鸟小李是xmu大x的学生了,可英语总数6x。四级考试临近了,临时抱佛脚的他买了本英语词汇,可是小李是个大穷人,随便街摊买了本盗版的新东方。回到宿舍才发现:书里的单词竟然是...
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
OJ习题.zip
这是洛谷OJ题库导出文件,希望大家下载看看
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
贪心算法 一般来说,贪婪算法有五个组成部分: 一个候选集:从中创建一个解决方案 一个选择函数:用于选择要添加到解决方案中的最佳候选项 一个可行性函数:用于确定候选项是否可以为解决方案做出贡献 一个目标函数...
杭州电子科技大学 oj离线版