并查集的入门与应用
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
一、前言
本文主要讲了并查集的概念、路径压缩讨论了一题多解的思路和一些例题。
二、并查集概念
- 并查集Disjoint Set一种非常精巧而实用的数据结构。
- 用于处理不相交集合的合并问题。
- 经典应用
- 连通子图
- 最小生成树 Kruskal 算法
- 最近公共祖先
【场景1】
- 有 n 个人他们属于不同的帮派
- 已知这些人的关系例如1号、2号是朋友1号、3号 也是朋友那么他们都属于一个帮派
- 问有多少帮派每人属于哪个帮派。
- 用并查集可以很简洁地表示这个关系。
【场景2】
有n个人一起吃饭有些人互相认识。
认识的人想坐在一起而不想跟陌生人坐。
例如A认识BB认识C那么A、B、C会坐在一张桌子上。
给出认识的人问需要多少张桌子。
1、并查集的初始化
- 定义 s[i] 是以结点 i 为元素的并查集。
- 初始化令 s[i]=i。(某人的号码是i他属于帮派 s[i])
def init_set(): #初始化
for i in range(N):
a.append(i)
#s=list(range(N)) #init_set()可以简化为这一行2、并查集的合并
- 例加入第一个朋友关系 (1,2)。
- 在并查集 s 中把结点 1 合并到结点 2也就是把结点 1 的集 1 改成结点 2 的集 2。
- 加入第二个朋友关系 (1,3)
- 查找结点1的集是2递归查找元素2的集是2
- 把元素2的集2合并到结点3的集3。
- 此时结点1、2、3都属于一个集。
- 加入第三个朋友关系 (2,4)
def merge_set(x,y): #合并
x=find_set(x)
y=find_set(y)
if x!=y:
s[x]=s[y]
3、并查集的查找
查找元素的集是一个递归的过程直到元素的值和它的集相等就找到了根结点的集。
def find_set(x):
if x!=s[x]:
return find_set(s[x])
else:
return x这棵搜索树可能很细长复杂度 O(n)变成了一个链表出现了树的 “退化” 现象。
4、初始化、查找、合并代码
def init_set(): #初始化
for i in range(N):
a.append(i)
def find_set(x):
if x!=s[x]:
return find_set(s[x])
else:
return x
def merge_set(x,y): #合并
x=find_set(x)
y=find_set(y)
if x!=y:
s[x]=s[y]
5、复杂度
- 查找 find_set()、合并 merge_set() 的搜索深度是树的长度复杂度都是 O(n)。
- 性能差。
- 能优化吗
- 目标优化之后复杂度 ≈ O(1)。
二、路径压缩
- 查询程序 find_set()沿着搜索路径找到根结点这条路径可能很长。
- 优化沿路径返回时顺便把 i 所属的集改成根结点。下次再搜复杂度是 O(1。
def find_set(x): #有路径压缩优化的查询
if x!=s[x]:
s[x]=find_set(s[x]) #递归实现
else:
return x
- 路径压缩整个搜索路径上的元素在递归过程中从元素 i 到根结点的所有元素它们所属的集都被改为根结点。
- 路径压缩不仅优化了下次查询而且也优化了合并因为合并时也用到了查询。
三、例题
1、蓝桥幼儿园lanqiaoOJ题号1135
【题目描述】
蓝桥幼儿园的学生天真无邪朋友的朋友就是自己的朋友。小明是蓝桥幼儿园的老师这天他决定为学生们举办一个交友活动活动规则如下小明用红绳连接两名学生,被连中的两个学生将成为朋友。请你帮忙写程序判断某两个学生是否为朋友。
【输入描述】
第 1 行包含两个正整数 N,MN 表示蓝桥幼儿园的学生数量学生的编号分别为1- N。之后的第 2- M+1 行每行输入三个整数 op,x,y。如果 op=1表示小明用红绳连接了学生 x 和学生 y。如果op=2请你回答小明学生 x 和学生 y 是否为朋友。
1<=N,M<=2×10^51<=x,y<=N。
【输出描述】
对于每个 op=2 的输入如果 x 和 y 是朋友则输出一行 YES否则输出一行 NO。
def init_set():
for i in range(N):
parent.append(i)
def find_set(x):
if x!=parent[x]:
parent[x]=find_set(parent[x])
return parent[x]
def merge_set(x,y):
x=find_set(x)
y=find_set(y)
if x!=y:
parent[x]=parent[y]
n,m=map(int,input().split())
N=800_005
parent=[] #并查集
init_set()
for i in range(m):
op,x,y=map(int,input().split())
if op==1:
merge_set(x,y)
if op==2:
if find_set(x)==find_set(y):
print("YES")
else:
print("NO")2、合根植物2017年决赛lanqiaoOJ题号110
【题目描述】
w 星球的一个种植园被分成 m×n 个小格子东西方向 m 行南北方向 n 列。每个格子里种了一株合根植物这种植物有个特点它的根可能会沿着南北或东西方向伸展从而与另一个格子的植物合成为一体。如果我们告诉你哪些小格子间出现了连根现象你能说出这个园中一共有多少株合根植物吗
【输入格式】
第一行两个整数 m,n用空格分开表示格子的行数、列数 (1<m,n<1000。接下来一行一个整数 k表示下面有 k 行数据 (0<k<100000)。接下来 k 行每行两个整数 a,b表示编号为 a 的小格子和编号为 b 的小格子合根了。格子的编号一行一行从上到下从左到右编号。
【输出格式】
输出一个整数表示答案。
【常规做法】
- 用并查集处理所有的合并
- 处理完后检查所有 S[i] = i 的数量也就是集等于自己的数量就是答案。
- 初始化时假设所有植物都不合根初始答案ans = m×n。
- 然后用并查集处理合根合根一次ans减一。
def find_set(x):
if x!=parent[x]:
parent[x]=find_set(parent[x])
return parent[x]
def merge_set(x,y):
x=find_set(x)
y=find_set(y)
if x==y: # 同根
return False
parent[y]=parent[x]
return True # 合根一次
m,n=map(int,input().split())
k=int(input())
parent=list(range(m*n))
ans=m*n
for i in range(k):
x,y=map(int,input().split())
if merge_set(x,y):
ans-=1
print(ans)3、修改数组2019年省赛lanqiaoOJ题号185
【题目描述】
给定一个长度为 N 的数组 A=[A1, A2,...,AN]数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,...,AN。当修改 Ai 时小明会检查 A 是否在 A1~Ai 中出现过。如果出现过则小明会给 Ai 加上1如果新的 Ai 仍在之前出现过小明会持续给 Ai 加1直到 Ai 没有在 A1~Ai 中出现过。当 AN 也经过上述修改之后显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组请你计算出最终的 A 数组。
【输入】
第一行包含一个整数 N (1<=N<=100000)第二行包含 N 个整数 A1, A2, ..., AN (1<=Ai<=1000000)。
【输出】
输出 N 个整数依次是最终的 A1, A2, ..., AN
【输入示例】
5
2 1 1 3 4
【输出示例】
2 1 3 4 5
功能把数组的数字转换为都不重复
数组 A = [A1, A2, ... ,AN]
依次修改 A2, A3, ..., AN
修改 Ai 时检查 Ai 是否在 A1~Ai 中出现过
如果出现过给Ai加上1
如果新的 Ai 仍在之前出现过持续给 Ai 加 1直到 Ai 没有在 A1~Ai-1中出现过。
1暴力法1
1<=N<=100000
每读入一个新的数就检查前面是否出现过每一次需要检查前面所有的数。共有 n 个数每个数检查 O(n) 次总复杂度 O(n^3)超时。
n=int(input())
a=[int(i) for i in input().split()]
for i in range(1,n): #从第2个开始a[1]
for k in range(i): #检查它前面的所有数做k次
for j in range(i):
if a[i]==a[j]:
a[i]+=1
for i in range(n):
print(a[i],end=' ')
#for i in a:
# print(i,end=' ')2暴力法2
n=int(input())
a=[int(i) for i in input().split()]
for i in range(1,n): #从第2个开始a[1]
for j in range(i): #检查它前面的所有数
while a[i] in a[0:i]:
a[i]+=1
for i in range(n):
print(a[i],end=' ')
#for i in a:
# print(i,end=' ')
3查重hash或set()
- 改进用hash。定义 vis[] 数组vis[i] 表示数字 i 是否已经出现过。这样就不用检查前面所有的数了基本上可以在 O(1) 的时间内定位到。
- 或直接用 set 判断是否重复也是 O(1)。
n=int(input())
a=[int(i) for i in input().split()]
s=set()
for i in range(n):
while a[i] in s:
a[i]+=1
s.add(a[i])
for i in range(n):
print(a[i],end=' ')
#for i in a:
# print(i,end=' ')
4新思路——并查集
本题特殊要求“如果新的 Ai 仍在之前出现过小明会持续给 Ai 加 1直到 Ai 没有在 A1~Ai-1 中出现过。” 这导致在某些情况下仍然需要大量的检查。
以 5 个 6 为例: A[]= {6,6, 6,6,6)。
第一次读 A[1]=6设置 vis[6]=1。
第二次读 A[2]=6先查到 vis[6]=1则把 A[2] 加 1变为 A[2]=7再查 vis[7]=0设置 vis[7]=1。检查了 2 次。
第三次读 A[3]=6先查到 vis[6]=1则把 A[3] 加 1 得 A[3]=7再查到 vis[7]=1再把 A[3] 加 1 得A[3]=8设置 vis[8]=1最后查 vis[8]=0设置 vis[8]=1。
........
检查了 3 次。每次读一个数仍需检查 O(n) 次总复杂度 O(n^2)。
- 本题用 Hash在特殊情况下仍然需要大量的检查。
- 问题出在 “持续给 Ai 加 1直到 Ai 没有在 A1~Ai-1 中出现过”。
- 也就是说问题出在那些相同的数字上。当处理一个新的 Ai 时需要检查所有与它相同的数字。
- 如果把这些相同的数字看成一个集合就能用并查集处理。
用并查集处理就非常巧妙了
用并查集 s[i] 表示访问到 i 这个数时应该将它换成的数字。
以 A[]= {6,6,6,6,6) 为例。初始化 set[i]=i
图(1)读第一个数 A[0]=6。 6 的集 set[6]=6。紧接着更新 set[6]=set[7]=7作用是后面再读到某个A[k] =6时可以直接赋值A[k]=set[6] =7。
图(2)读第二个数 A[1]=6。 6 的集 set[6]=7更新 A[1]=7。紧接着更新 set[7]=set[8]=8。如果后面再读到 A[k]=6或7 时可以直接赋值 A[k]=set[6]=8 或者 A[k]=set[7]=8.
- 只用到并查集的查询没用到合并。
- 必须是“路径压缩”优化的才能加快查询速度。没有路径压缩的并查集仍然超时。
- 复杂度O(n)
上面的处理还是很值得思考一下的。
def find_set(x):
if x!=parent[x]:
parent[x]=find_set(parent[x])
return parent[x]
N=1000002
parent=list(range(N))
n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
root=find_set(a[i])
a[i]=root
parent[root]=find_set(root+1) #加一
for i in a:
print(i,end=' ')4、七段码2020年省赛lanqiaoOJ题号595填空题
【问题描述】
七段数码管一共有 7 个发光二极管问能表示多少种不同的字符要求发光的二极管是相连的。
- 标准思路“灯的组合+连通性检查”
- 编码“DFS+并查集”
a b c d e f g
字符用数字表示
1 2 3 4 5 6 7
N=10 e=[[0]*N for i in range(N)] s=[0]*N vis=[0]*N ans=0 e[1][2]=e[1][6]=1 e[2][1]=e[2][3]=e[2][7]=1 e[3][2]=e[3][4]=e[3][7]=1 e[4][3]=e[4][5]=1 e[5][4]=e[5][6]=e[5][7]=1 e[6][1]=e[6][5]=e[6][7]=1 e[7][2]=e[7][3]=e[7][5]=e[7][6]=1 dfs(1) #从第一个灯开始深搜 print(ans)
- 灯的所有组合用 DFS 得到用 “自写组合算法”。
- 选或不选第 k 个灯就实现了各种组合。
- check() 函数判断一种组合的连通性。
def dfs(k): #深搜到第k个灯 if k==8: check() #检查连通性 else: vis[k]=1 #点亮这个灯 dfs(k+1) #继续搜下一个灯 vis[k]=0 #关闭这个灯 dfs(k+1) #继续搜下一个灯
- check() 函数判断一种组合的连通性。
- 连通性检查用并查集。
- 判断灯 i、j 都在组合中且相连那么合并到一个并查集。
- flag=1表示这个组合中的所有灯都合并到了同一个并查集说明它们是连通的。
def check(): global ans init() for i in range(1,8): for j in range(1,8): if e[i][j]==1 and vis[i]==1 and vis[j]==1: merge_set(i,j) flag=0 for j in range(1,8): if vis[j]==1 and s[j]==j: flag+=1 if flag==1: ans+=1
【完整代码】
def init():
for i in range(N):
s[i]=i
def find_set(x):
if x!=s[x]:
s[x]=find_set(s[x])
return s[x]
def merge_set(x,y):
x=find_set(x)
y=find_set(y)
if x!=y:
s[x]=s[y]
def check():
global ans
init()
for i in range(1,8):
for j in range(1,8):
if e[i][j]==1 and vis[i]==1 and vis[j]==1:
merge_set(i,j)
flag=0
for j in range(1,8):
if vis[j]==1 and s[j]==j:
flag+=1
if flag==1:
ans+=1
def dfs(k): #深搜到第k个灯
if k==8:
check() #检查连通性
else:
vis[k]=1 #点亮这个灯
dfs(k+1) #继续搜下一个灯
vis[k]=0 #关闭这个灯
dfs(k+1) #继续搜下一个灯
N=10
e=[[0]*N for i in range(N)]
s=[0]*N
vis=[0]*N
ans=0
e[1][2]=e[1][6]=1
e[2][1]=e[2][3]=e[2][7]=1
e[3][2]=e[3][4]=e[3][7]=1
e[4][3]=e[4][5]=1
e[5][4]=e[5][6]=e[5][7]=1
e[6][1]=e[6][5]=e[6][7]=1
e[7][2]=e[7][3]=e[7][5]=e[7][6]=1
dfs(1) #从第一个灯开始深搜
print(ans)
以上并查集的入门与应用
祝好