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

全文目录🧭

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

🚀传送锚点​

 💡思路点拨

🍞代码详解  

👶🏻并查集-蓝桥幼儿园

🚀传送锚点

 💡思路点拨

🍞代码详解  

🌼并查集-合根植物

🚀传送锚点

 💡思路点拨

🍞代码详解  

 🏰并查集-城邦

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

 💡思路点拨

🍞代码详解  

---

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

#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
'''

---

👶🏻并查集-蓝桥幼儿园

🚀传送锚点

​​​​​​​

 💡思路点拨

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

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

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

🍞代码详解  

#并查集-蓝桥幼儿园
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
'''

---

🌼并查集-合根植物

🚀传送锚点

​​​​​​​

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

 💡思路点拨

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

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

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

🍞代码详解  

#并查集-合根植物
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
'''

 🏰并查集-城邦

🚀传送锚点

​​​​​​​

 💡思路点拨

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

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

不知道大家有没有玩过俄罗斯套娃⛄？（一个套娃里面嵌套了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天，一起冲刺省赛一等奖！​​

​