5.5.2 并查集及优化

并查集维护不相交集合，支持 find(x) 找代表元与 unite(a,b) 合并。森林中每个结点指向双亲，根指向自身或存负的集合规模。未经优化的链可能很深；按秩/按大小合并把小树接到大树，路径压缩让查找沿途结点直接靠近根。

手工推演

初始 0..5 各自成集。合并(0,1)、(2,3)、(0,2) 后，0..3 同集；若按大小合并，可让较小根 2 接到根 0。执行 find(3) 路径压缩后，3 可直接指向 0。

结构与代码

int find(int x){return p[x]==x?x:p[x]=find(p[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);p[b]=a;sz[a]+=sz[b];}

两种优化同时使用时，均摊复杂度近似常数，严格为反阿克曼函数级。

错解反馈

合并原结点而不是各自根；路径压缩后不更新父指针；按大小比较错对象；用代表元编号大小推集合规模。

迁移练习

处理边 (0,1),(1,2),(3,4),(2,4)，最终有几个集合（含0..4）？答案1。独立验收：每次合并后画父数组并实跑连通性。