应用

在近乎O(1)的时间内快速的处理：

1. 将两个集合合并
2. 询问两个元素是否在一个集合之中

原理

每个集合用树的形式维护、每个集合的编号为根结点的下标、用一个数组存放集合中每个节点的父结点

如何判断树根？

if p[x] == x

如何求x的集合编号？

while p[x] ≠ x: x = p[x] //只要不是树根，就往上走

如何合并两个集合？

p[px] = py px、py为集合编号

优化：路径压缩

查找x的集合编号时，是会随着树的大小而找的越慢，因此有个优化就是：每次x找集合编号时，找完之后都会把沿路的节点的父结点都指向根结点

代码实现

N = 10010
p = [0] * N
# 初始化！
def init(p):
    for i in range(len(p)):
        p[i] = i

def find(p, x):# 返回x所在集合的编号 + 路径压缩优化
    if p[x] != x:
        p[x] = find(p[x]) # 找到的根节点都会被赋值到搜过的点
    return p[x] # 返回父结点

def union(p,x,y): #合并x，y集合
    p[find(p,x)] = find(p,y)