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
点此复制本页地址
【书院传真】品幸福滋味,享浓情时刻——第二届“色香味意形”书院烹饪大赛暨“芳菲四月”4月师生集体生日会圆满落幕酸甜苦辣咸,调出人生百味;油盐酱醋,烹出世间百态;煎炒烹炸,做出……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
【书院传真】凝聚团队精神,共筑“三长”团魂——2020-2021学年第二学期“楼长、层长、室长”三长训练营圆满落幕和煦的阳光透过稠密的树叶洒落下来,成了点点金色的光斑,一个个青春靓丽的……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
第57期书院说:藏在动画中的创造力创造力就是在原有事物的基础上,通过独特的方式创造出美好且适应人们需求的事物,创造源于生活且高于生活。4月15日10:00,晋中信息学院举办第57期“书院说……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
信院力量·书联】重温精彩瞬间,放飞青春梦想青春是绚丽的彩虹,以靓丽的色彩勾勒人生的美景,青春是美妙的乐章,以跳跃的音符谱写生活的章程。优美的风景装点着活力无限的书院青春,在春……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
2020-2021第二学期书院第五周活动纪实·我们一起“趣”书院青春是一场修行,在这场修行中学子与书院相遇,热情洋溢的少年在温暖的书院中稳步向前,不断成长,尽显青春风采.书院部3月31日14:3……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
2020-2021第二学期书院第六周活动纪实·我们一起“趣”书院我们在书院相遇、相识、相知,感受书院“家”的温暖,跟随书院的脚步,让我们一同回顾第六周书院生活足迹。书院部4月10日8:00,由晋……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
书院部第七周活动纪实·我们一起“趣”书院在书院,我们携手走过每一次温馨时刻都伴随着书院家人们的陪伴和关爱,与书院一同守望成长,砥砺前行。书院部3月23日—4月15日,晋中信息学院举办……
书院小源籽 山西农业大学信息学院书院部查看全文 >>
【书院传真】以阅读点亮心灯,让书籍润泽心灵——2021年世界读书日之阅读一小时活动顺利举办阅读,悦心,约未来;品读,渡己,探本真。今年4月23日是第26个世界读书日,晋中信息学院通识课……
书院小源籽 山西农业大学信息学院书院部查看全文 >>