关于find路径压缩后对应并查集的结构

来源：6-6 路径压缩 (Path Compression)

慕移动9586716

2021-05-21

回头重新看了一遍这部分内容，我有这么一个问题：就拿老师你在这一小节PPT中的例子吧，我们在find(4)的过程中进行了路径压缩，他会改变原有并查集的结构嘛？

int find(int p){
            assert( p >= 0 && p < count );
            // path compression 2, 递归算法
            if( p != parent[p] )
                  parent[p] = find( parent[p] );
                  return parent[p];
        }

写回答

1回答

liuyubobobo

2021-05-21

已采纳

改变了呀。

parent[p] = find( parent[p] );

所以，parent[p] 的值变了。

而没有路径的写法，你可以回顾一下，不会改变 parent[p]。

至于并查集在路径压缩的时候具体是怎么变的，再回顾一下 ppt 的动画呀。

继续加油！：）

慕移动9586716

非常感谢！

2021-05-21

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题

路径压缩的问题

回答 1

回答 1

回答 1

回答 1

回答 1