并查集

基本框架

并查集是一种树形数据结构，主要有以下的两个操作

• 查找一个元素位于那个集合
• 合并两个集合

用一个$fa$数组表示当前元素的祖先是谁

初始状态下$fa_i=i$

我们把一个集合记作这个集合组成的树的根节点，查询操作可以$O(n)$的完成

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

而$union$操作只需要把$fa[find(x)]$赋值为$find(y)$即可

但是这个时间复杂度显然不够优秀，考虑去优化它

路径压缩

显然，我们每次找祖先是都会把同样的一条路重复走过，这显然不是最优的，因为祖先不可能下降，所以可以在find时把$fa[x]$赋值为$find(fa[x])$来简化以后的查询

虽然表面上似乎这是小优化，但是路径压缩后的实际复杂度接近$O(1)$，基本是线性的

启发式合并

简单来说就是把小集合向大集合合并，而不将大集合向小集合合并

复杂度证明

建议参考Tarjan给出的证明