这篇文章主要介绍了C++的并查集如何实现的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++的并查集如何实现文章都会有所收获，下面我们一起来看看吧。并查集是一种多叉树，用于处理不相交的集合的合并与查询问题（判断）。通俗理解：在日常生活中，我们会因为某个人是自己的朋友，哪怕是朋友的朋友也是有朋友，会给予通融、 偏袒。而并查集的基本概念，就是判断某两个集合是否是“朋友”关系，并让两个集合成为“朋友”初始化：每个结点单独作为一个集合查询：求元素所在的集合的代免费云主机域名表元素，即根结点合并：将两个元素所在的集合，合并为一个集合合并之前，应先判断两个元素是否属于同一集合，用上面的“查询”来实现初始化:初始的时候每个结点各自为一个集合,father[i]表示结点 i 的父亲结点,如果 father[i]=i,我们认为这个结点是当前集合根结点（开始时每个节点根节点是他自己）。查找:查找结点所在集合的根结点,结点 x 的根结点必然也是其父亲结点的根结点（像是有递归的样子）。合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。上面三个操作是并查集常用的操作前面的并查集的复杂度实际上在有些极端情况会很慢。比如树的结构正好是一条链，那么最坏情况下，每次查询的复杂度达到了O(n) 。这并不是我们期望的结果。路径压缩的思想是，我们只关心每个结点的父结点，而并不太关心树的真正的结构（递归查找相当浪费时间）如下：当想去访问6的根节点时，要访问5的根节点，想去访问5的根节点，又要去访问4的根节点……….以此类推，此时并查集退化为线性。这样我们在一次查询的时候，可以把查询路径上的所有结点的father[i]都赋值成为根结点。只需要在我们之前的查询函数上面进行很小的改动关于“C++的并查集如何实现”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“C++的并查集如何实现”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注百云主机行业资讯频道。
这篇文章主要介绍了怎么用shell脚本设置日志格式的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇怎么用shell脚本设置日志格式文章都会有所收获，下面我们一起来看看吧。关于“怎么用shell脚本设置日志格式”这篇文章的内容就介绍到…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
