今天补题遇到了这个知识点，能想到这个方法但是自己没办法实现，所以来复习一下相关知识做个总结~

并查集，简单来说，合并两个集合，然后能迅速判断两个元素是否在同一集合中（查询某个元素的祖先结点）

时间复杂度可以达到 $O(logn)$

通过路径压缩和按秩合并的优化，可以使并查集算法达到$O(1)$

  1. 记录每个集合大小，将信息绑定到根结点（其余节点的信息对不对无所谓）
  2. 记录每个结点到根结点距离，将信息绑定到每个元素身上

板子
返回 x 的祖先结点，同时进行路径压缩，让 p[x] 直接指向祖先结点

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

实现方法：
首先所有元素各为一个集合，创建数组 p[i]，意为 i 的父结点，起初，p[i] 全部等于 i

  • 当两个元素 a b 进行合并时（实际上就是两个集合进行合并），让 a 的祖先结点的父结点等于 b 的祖先结点，a 的祖先结点直接指向 b 的祖先结点
    p[find(a)] = find(b);
  • 当询问两个元素 a b 是否在同一个集合中时，只需要看 a b 的祖先结点是不是同一个，也就是判断 find(a) == find(b) 是否成立