【蓝桥模板】——如何用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日
    浏览(47)
  • 【算法每日一练]-图论(保姆级教程篇7 最小生成树 ,并查集模板篇)#村村通 #最小生成树

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

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

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

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

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

    2024年02月11日
    浏览(40)
  • 并查集の进阶用法

    我们在处理问题的时候,可能会遇到一些需要维护每个元素所在的集合的问题,而并查集却恰好完美解决了这个问题。 对于普通的并查集,他支持的操作比较少,只有合并和查询,合并是指把两个集合合并成一个,而查询是询问两个元素是否在同一集合内;对于这两种操作,

    2024年02月02日
    浏览(41)
  • 数据结构---并查集

    这里可以使用生活中的一个例子来带着大家理解并查集,大家在上学的过程中肯定会发现一种现象,在开学之前大家谁也不认识谁每个人都是一个小团体,可是开学之后因为座位旁边有一个同桌,所以开学没多久你和同桌就会互相认识并且开心的玩在一起,那么这时就是两个

    2024年02月15日
    浏览(42)
  • 并查集

    并查集 并查集是用来判断两个元素是否属于同一个集合 即判断他们的根节点是否相同 1. 初始化 2.查询根节点 3.合并 集合变为一个长长的链时,查找变得十分麻烦,此时我们需要路径压缩 即每个人的直接根节点就是最上面的根节点 我们判断两个元素是否是同一个集合,看的

    2024年02月08日
    浏览(31)
  • C++:合并集合(并查集)

    一共有n个数,编号是1~n,最开始每个数各自在一个集合中。 现在要进行m个操作,操作共有2种: 1.“M a b”,将编号为a和b的两个数的所在的集合合并,如果两个数已经在同一个集合中则忽略这个操作 2.“Q a b”,询问编号为a和b的两个数是否在同一个集合中 第一行输入整数

    2024年02月13日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包