并查集被很多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)