学生梳理情况
①知道某些学生的学校。
例如:A是X校的学生。
②知道两个学生互为同学。
例如:学生A是学生B的同学。(所以我们也可以得到:B也是X校的学生)
现在要确定每个学生就读的学校,如何能够高效简洁的解决这个问题呢?
首先将学生和学校当作图中的点,把信息①当作是学校和学生的边,把信息②当作是连接2个学生的边。那么很明显,同校的学生理应在同一张连通图内,而学校就是这张连通图的标记。
如下图,X和Y是学校,ABCDE是学生,那么情况就一目了然——AB是X校的学生,CDE是Y校的学生。

最终我们只需要建图后跑连通图即可
拓展
在梳理完学生的开学日期后,学生的好朋友肯定不只是同一所学校的,有时候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函数的返回值是否相同:
