wordpress站点结构,中国建设银行手机网站下载,企业信息查询官网入口,做国外有那些网站比较好这是C算法基础-数据结构专栏的第二十九篇文章#xff0c;专栏详情请见此处。 由于作者即将参加CSP#xff0c;所以到比赛结束前将不再发表文章#xff01;
引入 并查集是一种可以快速合并查找集合的一种数据结构#xff0c;这次我们将通过三道题来详细讲解并查集#xff… 这是C算法基础-数据结构专栏的第二十九篇文章专栏详情请见此处。 由于作者即将参加CSP所以到比赛结束前将不再发表文章
引入 并查集是一种可以快速合并查找集合的一种数据结构这次我们将通过三道题来详细讲解并查集朴素版、维护并查集大小版和维护到祖宗节点距离版而这次我们要学习朴素版的并查集。 下面我们就来讲并查集的实现朴素版。
定义 并查集是一种用于管理元素所属集合的数据结构实现为一个森林其中每棵树表示一个集合树中的节点表示对应集合中的元素。
过程 例题合并集合 题目大意起初一共有个数每个数都各自在一个集合中。现在要进行个操作操作共两种将两个数所在的集合合并询问两个数是否在同一个集合中 操作合并和查找 并查集顾名思义它就是支持两种基本操作的数据结构并合并和查查找。它的原理就是用一个数组记录每个节点的祖宗节点通过对这个数组的更新实现数据之间的联系。刚开始所有节点的根都是它本身。 首先我们需要实现一个函数find()用来寻找一个节点的根方法很简单只需不断递归一直访问现在节点的祖宗节点直到访问到根节点即该节点的是本身。 首先是第一个操作合并。合并时只需要将其中一个节点的根的赋值为另一个节点的根。 第二个操作查找。查找两个节点是否在同一棵树上仅仅判断两个节点的find()是否相同即可。 Q为什么不直接比较呢 A因为在合并时若有两棵树进行合并可能中途的节点的不会被直接连到根上所以需要不断寻找才能找到最终的根。 优化路径压缩和按秩合并 接下来我们进行优化在实现find()函数的过程中很明显一路上经过的点都在这个集合中为了加快后续查询我们可以将其直接连到根上。这一优化我们称为路径压缩。这个优化大大的降低了时间复杂度。 有时题目需要保留原有的树的结构这时我们就不能采用路径压缩了。合并时我们可以在每棵树的根上记录树的层数把层数小的树合并到层数大的树很明显这样做可以减少合并后树的层数这叫做按秩合并。 由于路径压缩的优化程度比按秩合并要大所以我们一般仅仅采用路径压缩就足够了。课程中也只是提到了按秩合并并没有讲解所以在代码中我们也不采用按秩合并。
代码 下面给出朴素版并查集的实现代码
int p[N];int find(int x){if(p[x]!x) p[x]find(p[x]);return p[x];
}for(int i1;in;i) p[i]i;p[find(a)]find(b); 代码解释 第一行是存储每个节点的祖宗节点的数组find()函数的作用是寻找根节点for循环中的内容的作用是初始化最后一行的作用是合并。
上一篇-Trie树之最大异或对问题 C算法基础专栏文章 下一篇-并查集的实现维护并查集大小版版 每周一更新一篇文章内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞关注一下呗~
