Skip to content

Ch6 路径压缩 #31

@SamZhangQingChuan

Description

@SamZhangQingChuan
query(element) {
        var p = this.parents;
        while (element !== p[element]) {//如果一样就到顶,否则继续往上找
          p[element] = p[p[element]];
          element = p[element];
        }
        return element;
}

这段完全是错的,路径压缩会把 element 的所有祖先的 parent 都设成根
我的 c++写法如下,你可以把他改成 js 版

int root(int x) { return data[x] == x ? x : data[x] = root(data[x]); }

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions