并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:
- 合并(Union):把两个不相交的集合合并为一个集合。主要思想是路径压缩,把沿途的每个节点的父节点都设为根节点
- 查询(Find):查询两个元素是否在同一个集合中。
合并(路径压缩)示意图:
#核心代码 import numpy as np # 初始化数组 存放父节点 def init(n): global fa fa = np.arrage(0,n+1,1) # 查找 路径压缩 def find(num): if fa[num] != num: fa[num] = find(fa[num]) return fa[num] # 合并 def union(a,b): fa[a] = find(b)