CSP-S 题库并查集程序阅读题

阅读以下并查集 find(含路径压缩)实现,回答子问题:

程序阅读题 第 48 题 · CSP-S 提高级 初赛题库
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)合并
    解析:避免树退化成链,保证高效。

同知识点练习

本题收录于「CSP-S 提高级 初赛题库」,共 51 道题,全部提供答案与解析。可进入在线练习系统按知识点随机组卷、自动批改并归集错题。

进入在线练习 查看完整试卷 本类全部题目