并查集
并查集支持的操作:
- 合并:将两个子集合合并,要求两个子集合互不相交,否则不执行合并操作
- 查找:查找某个元素x所在的子集合,返回该子集合的名字。常用于把询问两个元素是否在一个集合当中。
复杂度: 近乎O(1)
基本原理
每一个集合用一颗树来表示,每一个集合的编号为其根节点的编号,每一个节点存储器它的父节点是谁。p[x]表示父节点。
p数组:数组元素的下标表示元素编号,数组元素的值表示其下标为编号的元素的父节点的节点编号(路径压缩情况下,即指向根节点),只有根节点元素的下标和值相同。借助p数组形成了树的结构。
问题1: 如何判断树根? if p[x] == x
问题2: 如何求得集合编号? while (p[x] != x) x = p[x]
问题3:如何合并两个集合? p[x] = y
路径压缩优化
def find(x):
"""找到元素的根节点 并将路径上所有的元素的父节点都直接指向根节点"""
if p[x] != x: p[x] = find(p[x])
return p[x]
if __name__ == '__main__':
n,m = map(int,input().split())
p = [i for i in range(n+1)] # p数组 最初都指向自己
for idx in range(m):
op,f,s = input().split()
f = int(f)
s = int(s)
if op == "Q":
if find(f) == find(s):
print("Yes")
else:
print("No")
else:
p[find(f)] = find(s)