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

Question

回头重新看了一遍这部分内容，我有这么一个问题：就拿老师你在这一小节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];
        }

Answer 1

liuyubobobo 2021-05-21 11:14:50

改变了呀。

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

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

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

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

继续加油！：）

• 提问者 慕移动9586716 #1

  非常感谢！