并查集 2024.3.30
总言之:将数组的值改为根节点的坐标,只要值和下标相同就是根节点,不相同就继续访问,访问到根节点,若根节点相同就是同一集合
y总基础整理
1、合并两个集合
2、询问两个元素是否在同一个集合
近乎O(1)的时间复杂度完成
每个集合用一棵树表示,树根编号就是整个集合编号,每个节点存储他的父节点,
问题1:如何判断树根:if(p[x] == x )
问题2:如何求x的集合编号:while(p[x]!=x) x = p[x];
问题3:如何合并两个集合:px是x的集合编号,py是y的集合编号。p[x]=y。修改集合编号即可
优化方法:
按秩合并及路径压缩
但是按秩合并很少用
采用路径压缩的方法解决问题二时间复杂度的问题
Acwing 836合并集合代码
"""
并查集的实现方法:将存储的数据合并至一个根节点处,即是路径压缩,节约时间,
将数组中该元素的值改为同一根节点,只要根节点相同即是同一个集合
"""
from sys import stdin #stdin是python内置的读取包,用于读取,数据量大可以节约时间
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]#返回根节点,最终找到下标和值相同的就是根节点
def main():
#首先读取数的数量
for i in range(m):
op, a, b = stdin.readline().split() # op是操作方法,a、b是数 m 1 2
a,b = int(a), int(b)
if op == "M":
if find(a) != find(b): #如果根节点不相等,则继续寻找根节点
p[find(a)] = find(b)#将该节点改成合并节点的名称
elif op == "Q":#寻找,如果根节点相同,就是根节点位置
if find(a) == find(b):
print("Yes")
else:
print("No")
if __name__ == "__main__":
n,m =map(int,input().split())#4 5
#初始化
p = [i for i in range(n+1)]#0 1 2 3
main()
同理:对于亲戚问题,我们也可以按照此模版,思路完全相同,采用并查集解决此问题
来自acwing1249
def find(m):
if p[m]!=m:
p[m]=find(p[m])
return p[m]
def main():
for i in range(m):
a,b = map(int,input().split())
if find(a)!=find(b):
p[find(a)]=find(b)
k = int(input())
for j in range(k):
a,b = map(int,input().split())
if find(a)==find(b):
print("Yes")
else:
print("No")
if __name__=="__main__":
n,m = map(int,input().split())
p = [i for i in range(n+1)]
main()