算法与程序设计训练第二天

2022年6月26日，”理实交融”——勇攀程序竞赛之巅团队正式开始了社会实践的第二天，大家开始了第二天的训练，今天也是四道比较简单题目，有二分查找、递推、并查集，队员们都能够积极去做题，完成任务。

今天学习的有并查集，并查集是一种树形的结构，这种数据结构是把一些元素按照一定的关系组合在一起。比如在亲戚关系的场景下，并查集是由一个跟节点（根节点指向自己）和所有他的子节点（可能是他的孩子节点或者子孙节点）组成。在信息学竞赛中，并查集是一种不可忽视的一部分内容，把最近几年的NOI和NOIP复赛题目大致浏览了一遍，发现有好几道应用并查集的题目，因此本文由浅入深的介绍并查集在编程中的巧妙应用。什么是并查集？并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，并就是按一定顺序将属于同一组的元素所在的集合合并。并查集的主要操作：

1、初始化：把每个点所在集合初始化为其自身；

2、查找：查找元素所在的集合即根节点；

3、合并：将两个元素所在的集合合并为一个集合，合并两个不相交集合判断两个元素是否属于同一集合。并查集进行n次查找的时间复杂度是O（n）（执行n-1次合并和m≥n次查找）。其中是一个增长极其缓慢的函数，它是阿克曼函数（AckermannFunction）的某个反函数。它可以看作是小于5的。所以可以认为并查集的时间复杂度几乎是线性的。今天学的知识我们要学会去运用，去应用在我们的生活当中，来处理解决一些实际问题。

http://www.dxsbao.com/shijian/448632.html 点此复制本页地址