【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

这篇具有很好参考价值的文章主要介绍了【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 大家好,我是爱分享的小蓝,欢迎交流指正~ 

【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

全文目录🧭

👩‍👩‍👦并查集-亲戚问题

🚀传送锚点​

 💡思路点拨

🍞代码详解  

👶🏻并查集-蓝桥幼儿园

🚀传送锚点

 💡思路点拨

🍞代码详解  

🌼并查集-合根植物

🚀传送锚点

 💡思路点拨

🍞代码详解  

 🏰并查集-城邦

🚀传送锚点​​​​​​​

 💡思路点拨

🍞代码详解  


并查集=合并成一家人+查找最大的爸爸

#7行并查集模板
def root(x):                #查找x的祖先是谁(查找根节点)
    if p[x]!=x:             #如果发现x的爸爸不是自己
        p[x]=root(p[x])     #递归找x的爸爸,直到找到最大的爸爸为止
    return p[x]             #返回祖先(祖先上面没爸爸,自己是根节点)
def union(x,y):             #合并成一家人 (合并两个结点)
    if root(x)!=root(y):    #如果祖先不同,不是一家人 (x和y的根结点不同)
        p[root(x)]=root(y)  #现在让x的祖先认y的祖先为爸(根节点x指向根节点y)

👩‍👩‍👦并查集-亲戚问题

🚀传送锚点​​​​​​​

 💡思路点拨

老规矩,先来一道并查集的经典例题「亲戚」,熟悉一下解决问题的4步基本流程~

1、默写模板:考前先把模板一敲,以防自己考试时一紧张忘了,那也就寄了。

2、输入参数:输入题目里的一堆参数,具体方法详见输入输出,这里不多赘述了。

3、建立关系:建立亲戚关系union(x,y),让x的祖先认y的祖先当爸爸,相亲相爱一家人。

4、判断关系:判断亲戚关系root(x)==root(y),判断它们是否是同源生,共有一个祖先。

🍞代码详解  

#并查集-亲戚问题
#1.默写模板
def root(x):
    if p[x]!=x:
        p[x]=root(p[x])
    return p[x]
def union(x,y):
    if root(x)!=root(y):
        p[root(x)]=root(y)
#2.输入参数         
n,m,p=map(int,input().split())#n:人数 m:亲戚关系数 p:询问次数
a=[list(map(int,input().split())) for i in range(m)]
#a=[[1, 2], [1, 5], [3, 4], [5, 2], [1, 3]]
b=[list(map(int,input().split())) for i in range(p)]
#b=[[1, 4], [2, 3], [5, 6]]
p=[i for i in range(n+1)]#建立编号1~6
#p=[0, 1, 2, 3, 4, 5, 6]
#3.建立关系
for i in a:#建立亲戚关系
    union(i[0],i[1])
#p=[0, 5, 5, 4, 4, 4, 6] 1号~5号是一家人
#4.判断关系
for i in b:#判断亲戚关系
    if root(i[0])==root(i[1]):
        print("Yes")#[1, 4]Yes #[2, 3]Yes
    else:
        print("No")#[5, 6]No

'''
样例输入:
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

样例输出:
Yes
Yes
No
'''

👶🏻并查集-蓝桥幼儿园

🚀传送锚点

​​​​​​​【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

 💡思路点拨

上题学会了判断亲戚关系,现在来判断朋友关系~

这次虽然换了一种形式,但换汤不换药,还是熟悉的配方——「​​​​​​​并查集

相信聪明的你,一定能轻松掌握!(´▽`ʃ♡ƪ)

🍞代码详解  

#并查集-蓝桥幼儿园
def root(x):
    if p[x]!=x:
        p[x]=root(p[x])
    return p[x]
def union(x,y):
    if root(x)!=root(y):
        p[root(x)]=root(y)   
n,m=map(int,input().split())
p=[i for i in range(n+1)]
for i in range(m):
    op,x,y=map(int,input().split())
    if op==1:
        union(x,y)
    else:
        if root(x)==root(y):
            print("YES")
        else:
            print("NO")

'''
样例输入:
5 5 
2 1 2
1 1 3
2 1 3
1 2 3 
2 1 2

样例输出:
NO
YES
YES
'''

🌼并查集-合根植物

🚀传送锚点

​​​​​​​【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

 💡思路点拨

依然还是并查集,这次来判断植物关系了。

并查集的题目千变万化,但它的本质是不变的。归根到底就是判断多个结点的关系

掌握了一眼看透事物本质的能力,不管来一段啥关系,你都能轻松看出是并查集关系。

🍞代码详解  

#并查集-合根植物
def root(x):
    if p[x]!=x:
        p[x]=root(p[x])
    return p[x]
def union(x,y):
    if root(x)!=root(y):
        p[root(x)]=root(y)
m,n=map(int,input().split())
k=int(input())
p=[i for i in range(m*n+1)]
for i in range(k):
    x,y=map(int,input().split())
    union(x,y)          #两个植物连根
ans=0
for i in range(1,m*n+1):
    if root(p[i])==i:   #如果自己的根不变
        ans+=1          #植物数+1
print(ans)
'''
样例输入:
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

样例输出:
5
'''

 🏰并查集-城邦

🚀传送锚点

​​​​​​​【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)

 💡思路点拨

城邦这道题是前年省赛的第五题,有亿点难度,小蓝之前太菜了不会做(/▽\)

现在学会并查集成为老鸟后,终于有能力可以解释一波了(╹ڡ╹ )

不知道大家有没有玩过俄罗斯套娃⛄?(一个套娃里面嵌套了N多个套娃的那种)

其实解题也是一样,本质就是套娃思维:一个知识点嵌套另一个知识点。

所以搞懂里面嵌套的所有知识点,问题就全解决了。

那么城邦有多少层套娃呢?

大概有三层:城邦=并查集+最小生成树+数论

并查集:合并城邦,查找桥是否装饰。

最小生成树:花最小的钱,装饰每一座桥。

数论:题目给出的计算权值函数。

看穿了题目隐藏的这三层套娃,就能轻松得分啦~

(总体思路讲解完毕,具体细节详见代码)

🍞代码详解  

#并查集-城邦
def root(x):
    if x!=p[x]:
        p[x]=root(p[x])
    return p[x]   
def union(x,y):
    if root(x) != root(y):
        p[root(x)]=root(y)  
              
def cost(x,y):#计算权值
    s=0
    while x or y:
        if x%10!=y%10:
            s+=x%10+y%10
        x//=10
        y//=10
    return s
    
p=[i for i in range(2022)] #p代表1~2021个城邦
edge=[(i,j,cost(i,j)) for i in range(1,2022) for j in range(1,2022)]#edge代表桥
#edge=[(1, 1, 2), (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6)]
edge.sort(key=lambda x:x[2]) #sort:按权值cost(i,j)从小到大排序
#edge=[(1, 1, 2), (1, 10, 2), (1, 11, 2), (1, 100, 2), (1, 101, 2)]

cnt,ans=0,0
for i in edge:                  #装饰2020座桥
    if root(i[0])!=root(i[1]):  #如果两个城邦的桥没装饰
        union(i[0],i[1])        #装饰一座桥,连接两个城邦        
        cnt+=1                  #桥梁计数器+1
        ans+=i[2]               #费用权值相加
    if cnt==2020:               #直到装饰满2020座桥
        break                   #结束  
             
print(ans)                      #4046      

  ​​ 友友们,备战蓝桥最后6天,一起冲刺省赛一等奖!​​

【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)文章来源地址https://www.toymoban.com/news/detail-408448.html

到了这里,关于【蓝桥模板】——如何用7行代码,优雅地拿捏并查集?(并查集模板)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 并查集(详细解释+完整C语言代码)

    目录 1概论 2.树的表现形式 3.代码实现 3.1创立集合 3.2合并 3.3查询 3.4路径压缩 第一个方法:查找时优化 第二个方法:合并时优化(加权标记法) 4.完整代码 4.1优化前  4.2优化后 并查集是一种十分精巧且实用的 树形 数据结构,它主要处理一些 不相交集合的合并与查询 问题

    2024年03月15日
    浏览(46)
  • 【算法每日一练]-图论(保姆级教程篇7 最小生成树 ,并查集模板篇)#村村通 #最小生成树

    目录 题目:村村通 并查集  题目:最小生成树 kruskal算法 prim算法          先引入问题: 要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的 任意两个之间都可以通信 ,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要 使铺设光

    2024年02月04日
    浏览(76)
  • 代码随想录图论并查集 第七天 | 685.冗余连接II

    代码随想录图论并查集 第七天 | 685.冗余连接II 一、685.冗余连接II 题目链接:https://leetcode.cn/problems/redundant-connection-ii/ 思路:684.冗余连接中是连通且无环的无向图可直接使用并查集模板,如果想判断集合中是否有环,且那条边构成环,只需要每次加入并查集之前先判断一下是

    2024年02月06日
    浏览(52)
  • 并查集(种类并查集,带权并查集)

    链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网   动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所

    2024年02月11日
    浏览(38)
  • 【数据结构】并查集

    并查集是简单的数据结构,学会并查集,为图打好基础。 是树状的数据结构,用于处理相交集合的合并与查询 通常用森林表示,一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合 查看两个元素是否属于同一个集合 将两个集合归并成一个集合 集合的个数 假

    2024年02月19日
    浏览(36)
  • 【高阶数据结构】——并查集

    在一些应用问题中, 需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并 。在此过程中要 反复用到查询某一个元素归属于那个集合的运算 。适合于描述这类问题的抽象数据类型称为 并查集

    2024年02月16日
    浏览(37)
  • 力扣--并查集547.省份数量

    思路分析: 首先定义变量 fa 用于记录并查集,以及城市数量 n 。 定义了并查集的两个函数, find 用于查找节点的根节点, togother 用于合并两个节点所在的集合。 在公共函数 findCircleNum 中,初始化并查集,然后遍历 isConnected 数组,将相连的城市进行合并。 最后使用 visited

    2024年03月26日
    浏览(32)
  • 相似图片分类 [华为]【并查集】

    题目描述: 小明想要处理一批图片,将相似的图片分类,他首先对图片的特征采样,得到图片之间的相似度,然后 按照以下规则判断图片是否可以归为一类: 1)相似度0表示两张图片相似; 2)如果A和B相似,B和C相似,但A和C不相似,那么认为A和C间接相似,可以把ABC归为一

    2024年04月12日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包