从一道小米面试题看并查集

2017-07-01 23:38 阅读 998 次 评论 0 条

小米面试题

已知有n个人和m对好友关系存储于r中,如果两个人是直接或间接的好友,则认为他们属于同一个朋友圈,编程求出这n个人里一共有多少个朋友圈?

比如:n=5,m=3,r={{1,2},{2,3},{4,5}},则认为1、2属于一个朋友圈,2、3是一个朋友圈,4、5是一个朋友圈,则1、2、3属于同一个朋友圈,4、5属于另一个朋友圈,共有两个朋友圈。

并查集的实现过程

并查集是一种树形数据结构,用于处理一些不相交集合的合并及查询,常以森林来表示。

是让每个元素构成一个单元素的集合,也就是按一定顺序将属于同一组的元素所在的集合合并。

下面我们使用上述例子加以说明合并过程:

① 编号。底层数据结构采用vector开辟大小为6的空间,并将每个值初始化为-1,表示元素是一个单独的集合(多开辟下标为0的空间是为了方便计算)。

② 合并。将{1,2}合并成一个集合,将下标为2的值加到下标为1处,再更新下标为2的值,即根节点为1。

③ 与②同理,{2,3}合并时,先找到两者的根节点,剩下操作与②一致。但是要注意的是:如果直接让2作为3的根,势必会增加森林的高度,不利于搜索,因此,我们让1作为2、3的根。

④ 同理,让{4,5}进行并集操作,得到两个不同的集合。

源代码及注释

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:从一道小米面试题看并查集 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情