人与人的关系——利用“并查集”展现(一)

人与人的关系——利用“并查集”展现(一)

深圳的学校最近终于是陆续开学了。

讲个笑话,小毕老师的朋友圈也充满着老师的“开心”、家长的“解脱”和学生的“苦恼”。

不过和熟识的学生打趣时,发现自己搞错了几个学生的开学日期,反倒是被对方打趣了。

痛定思痛,小毕老师我决定好好的梳理一下学生的情况。

为了简化,暂且把关系只梳理为两种:

学生梳理情况

①知道某些学生的学校。

例如:A是X校的学生。

②知道两个学生互为同学。

例如:学生A是学生B的同学。(所以我们也可以得到:B也是X校的学生)


现在小毕老师手中摆满了这两类的信息,现在要确定每个学生就读的学校,如何能够高效简洁的解决这个问题呢?


回顾

如果说之前有读过小毕老师的文章“由疫情出行延申到有关地图的计算机算法”(点击可阅读文章)的读者,可能已经发现,本次的问题和前文中”判定区域是否连通“实际上可以归类于同一个问题

首先将学生和学校当作图中的点,把信息①当作是学校和学生的边,把信息②当作是连接2个学生的边。那么很明显,同校的学生理应在同一张连通图内,而学校就是这张连通图的标记。

如下图,X和Y是学校,ABCDE是学生,那么情况就一目了然——AB是X校的学生,CDE是Y校的学生。


人与人的关系——利用“并查集”展现(一)


最终我们只需要建图后跑连通图即可。然后根据学校对连通图内点打标记即可,这里可以参考“前文”(点击可阅读文章)对color数组染色的做法即可。本文不过多赘述代码。


拓展

在梳理完学生的开学日期后,小毕老师又有了一个思考:学生的好朋友肯定不只是同一所学校的,有时候A和C虽然不是同校,但是A和C确是好朋友;有时候C和D同校,但是两人却根本不认识。

小毕老师心想,既然是和学生做朋友,那更加需要了解学生的交际圈,所以小毕老师又是收集了一波朋友圈消息,获得了大量信息。

形式如下:

A和B是朋友。

特别的,小毕老师发现,当A和C是朋友,A和B也是朋友,那么B和C会慢慢的通过A也变成好朋友。所以可以直接认为B和C也是朋友。


每过一段时间,小毕老师都想知道其中两个学生是否是朋友。而每天都有新的学生变成朋友。


思考

首先问题已与连通图不同。因为有可能今天询问D和C,不是朋友,但是明天D和B成为了朋友,那么D就和ABC都是朋友了。如果染色后,2个图连通,那么就需要把另外一张图的颜色全部改变,这时非常麻烦的事情。

怎么能够更简单的解决呢?


解决

回过头想一个问题。我们是如何解决学生就读学校问题?

我们采用了以学校为颜色,标记所有学生的方式。那么实际上对于这一张连通图来说,我并不需要标记颜色,因为学校是作为一个点仍然存在于这张图中,是这个连通图和其他连通图不同的标志。

我们能不能把”标志“这种思想继承过来?那么谁作为”朋友圈“的标志?

这里我们用树的形式来维护”朋友圈“信息。(问题①:读者们可以结合下文思考一下这里为什么需要用树形结构),那么我们就可以利用树根作为一个”朋友圈“集合的标记。所以树根便是我们的标志,而为了更加方便的维护树,能够让所有结点都能找到树根,我们采用的维护方式是——存储每个结点的父亲。

并且在最开始时,让每个结点的父亲都指向自己,也就是出现了”我是我的父亲“这种自环的形式,即”我“就是根——因为根结点是没有父亲的。


人与人的关系——利用“并查集”展现(一)


以及是如何通过递归父亲的方式找到树根的方式:


人与人的关系——利用“并查集”展现(一)



还有最后一个问题,那就是建边,也就是2个人成为朋友——把两棵树合并为一棵树:


人与人的关系——利用“并查集”展现(一)



最终,当遇到查询问题时,只需要判定2个人是否处在同一集合,也就是同一树内,也就是树根是否相同,也就是fnd函数的返回值是否相同


人与人的关系——利用“并查集”展现(一)


总结

其实今天接触到的算法思想叫做“并查集”。可以非常快的维护集合的合并与查询问题。(问题②:但是以上的代码还是有着一些致命的问题和遗漏,读者能否发现呢?)

为了防止篇幅过长,本文先止步于此,剩余的内容将在续文中亮相。

敬请期待。

人与人的关系——利用“并查集”展现(一)


程序语言提升班

程序语言提升班详情介绍

学员要求

学员已掌握基本的C++语言知识,包括简单的顺序、分支、循环等结构,此外能用基础编写代码解决部分编程问题。

课程内容

主要以算法为重点,帮助学生进一步了解计算机存储和运算方式。课程中教授学生数组、向量、字符串等程序语言,提升学生对程序算法的知识储备。


上课时间

每周六上午9-12点

上课地点

深圳市南山区G&G创意社区BEEPLUS

人与人的关系——利用“并查集”展现(一)

师资介绍

秦老师,哈尔滨工业大学(双一流大学)计算机专业。

获奖经历:高中时期获得NOIP提高组省级一等奖,大学期间共获得ICPC区域赛一金两银两铜,南科大第二届程序设计竞赛三等奖,“远光杯”粤港计算机程序设计大赛决赛二等奖,高教社杯全国大学生数学建模竞赛省级二等奖;

教学经历:大学时为ICPC校队队长,负责新进队员的教学和培训;曾担任哈工大【深圳】第一、二届程序设计竞赛主要负责人;在毕莘2年的工作期间多次担任程序语言基础、算法阶段课程的主讲教师;

教学特色:班课授课经验丰富,教学方式灵活变通,授课思路清晰,深入浅出易于学员理解。逻辑思维强,善于引导学员解决复杂的问题,语言严谨,认真负责。


课表详情:

人与人的关系——利用“并查集”展现(一)

(疫情期间课程将根据相关部门颁布的规定作出调整)


详情可扫描二维码咨询了解

人与人的关系——利用“并查集”展现(一)

毕莘教育咨询(深圳)有限公司围绕信息学竞赛普及组、提高组、省赛、国赛进行培训,同时提供与信息学相关的高校自主招生政策咨询。教研团队由国内顶校师资构成,深圳本地教学团队由来自清华、北大等顶尖名校的硕士、博士研究生及NOI、ACM- ICPC退役选手组成。自成立已开展多次培训,服务学生数百人次。

点击下方阅读原文可了解更多

原创文章,作者:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司,如若转载,请注明出处:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司

联系我们

教务老师:余老师
联系电话(微信同号):14774755240
在线咨询:点击QQ在线咨询

QR code