判断我绘制的不相交集结构可视化图(含link操作后)是否正确
不相交集作业验证指南
问题1:初始不相交集结构核对
根据给定的索引数组 i = [0 1 2 3 4 5 6 7 8 9] 和父数组 p[i] = [2 2 2 3 4 4 4 7 3 7],初始不相交集的结构应该是4个独立集合:
- 集合1:{0, 1, 2},根节点为2(
p[2] = 2),0和1的父节点均指向2 - 集合2:{3, 8},根节点为3(
p[3] = 3),8的父节点指向3 - 集合3:{4, 5, 6},根节点为4(
p[4] = 4),5和6的父节点均指向4 - 集合4:{7, 9},根节点为7(
p[7] = 7),9的父节点指向7
你可以直接对照自己绘制的图,检查每个节点的父指向是否完全匹配上述关系,以及根节点的标识是否正确。
问题2:带高度控制的lazy linking link(1,9)操作核对
带高度控制的lazy linking(无路径压缩)的核心规则是:仅修改两个集合根节点的指向,且优先将高度(rank)更小的树的根指向更高的树的根;若高度相同,则合并后新根的高度加1。具体操作步骤如下:
- 找到节点1的根:1 → 2(根节点,此时该树的rank为1——初始单节点rank为0,合并0、1到2后,rank更新为1)
- 找到节点9的根:9 → 7(根节点,该树的rank同样为1——合并9到7后rank更新为1)
- 合并两个根节点:由于两棵树rank相同,任选一个根作为新的根(比如将2的父指向7),并将新根(7)的rank加1(变为2)
- 关键注意点:无路径压缩意味着除根节点2的父指向改变外,其他所有节点的父指向保持初始状态不变(比如0的父还是2,1的父还是2,9的父还是7)
你可以对照自己的图,检查上述几点是否符合:根节点的指向修改是否正确,rank的更新是否到位,其他节点的父指向是否未被改动。
内容的提问来源于stack exchange,提问作者aha
相关产品推荐
相关产品推荐

