int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
- 当 fa[x]==x 时说明什么?答案:x 是所在集合的根节点解析:根节点的父指针指向自己。
- 路径压缩的作用是什么?答案:把查找路径上的节点直接挂到根,扁平化集合树解析:后续 find 接近 O(1)。
- union(合并)时通常还需配合什么策略以控制树高?答案:按秩(rank)或按大小(size)合并解析:避免树退化成链,保证高效。