【蓝桥杯】考前押题–并查集

🎉考前冲刺🎉 🎠1、合根植物 🎏2、亲戚 &#…

🎉考前冲刺🎉

🎠1、合根植物

🎏2、亲戚

🧵3、七段码


✏️记笔记:

并查集属于高级算法的一种,但是根据历年省赛真题来看,只要掌握了该模板,那几乎就是送分题哦,我将从这三道经典的并查集题目来带大家学习并查集模板!!

🎠1、合根植物

🎯问题描述

样例输入

样例输出

其合根情况参考下图:

💦题解分析:

(1)这是一道非常适合入门的并查集题目,简单易懂,模板十分清晰

(2)我来给大家分析一下模板的三要素:

1、初始化每一个父节点(即i的父节点为i自身)

2、Findfather()函数,用来寻找该节点的“祖宗”节点(一直往上寻找根节点)

3、union()函数,用来合并两个节点(将a的祖宗节点设置为b,ab就属于一个集合了)

(3)博主解释下面这行代码,当我们不断地合并节点后,每一个“子节点”的“父节点”都最终指向根节点那么我们怎么判断一共有多少个集合呢?我们不难发现一个集合中只有其根节点的父节点是指向自己的,那就好办了,当有一个节点其父节点等于自己,那么就代表有一个集合,也就是下面的这行记录集合数量的代码了

🎏2、亲戚

🎯问题描述

输入

输出

💦题解分析:

(1)该题是来源于洛谷的一道蛮经典的并查集入门题

(2)该题官方给的答案是用按秩合并来做的,博主为了让大家更好地理解并查集模板,采用传统解法

(3)聪明的小伙伴不难发现该题代码中的:

gx()函数就是上道题目的union()函数

find函数就是上道题目的Findfather()函数

(4)套路可谓是一毛一样,即使我们不会按秩合并,用常规的并查集模板也可以给它秒了

(5)注意看find()函数中使用了一行代码进行路径压缩(父节点直接指向根节点),优化了查找的复杂度

🧵3、七段码

🎯问题描述

💦题解分析:

(1)这个题目是一道填空题,比较综合(dfs+并查集),考察难度不输一般大题

(2)用二维数组模拟灯泡i和灯泡j的相邻情况(相邻为1)

(3)dfs枚举每一个灯的亮灭组成的所有情况(一共有2^7种可能)

(4)解释一下下面这行代码,当有且仅有一种联通亮灯情况的时候才合法,这个时候ans++

举个例子:

a和b构成一种联通;e和d构成一种联通,cnt=2,这个时候不符合题意,直接pass

🚀写在最后

距离蓝桥杯只有四天啦!!

博主争取再更一篇BFS的押题篇,希望大家多多支持!✨

最后,博主想送给大家一句话:

你逆光而来

配得上所有的美好

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/1397.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部