并查集

概念：并查集（DSU）维护若干不相交集合，支持查询两个元素是否连通和合并两个集合，常用于动态连通性与 Kruskal 算法。

关键步骤

初始化每点为自己的父亲；find 沿父指针到根并路径压缩；合并时把一个根挂到另一个根，按集合大小合并可控制树高。

vector<int> fa,sz;
int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); }
void unite(int a,int b){
    a=find(a); b=find(b); if(a==b) return;
    if(sz[a]<sz[b]) swap(a,b);
    fa[b]=a; sz[a]+=sz[b];
}

复杂度

路径压缩配合按大小合并后，m 次操作总时间 O(m α(n))，其中 α 为极慢增长的反阿克曼函数；存储为 O(n)。普通并查集不支持删除边。