当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 关于并查集的路径压缩(Path Compress)优化

关于并查集的路径压缩(Path Compress)优化

2018年05月31日  | 移动技术网IT编程  | 我要评论

之前在CSDN看到一篇很受欢迎的讲解并查集的博文，其中自然用到了路径压缩：

int pre[1000];
int find(int x){
    int root = x;
    while(pre[root]!=root)
        root = pre[root];
    int i = x,j;
    while(i!=root){      //path compress
        j = pre[i];
        pre[i] = root;
        i = j;
    }
    return root;
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx!=fy)
        pre[fx] = fy;
    else
        return;
}

你也许会发现问题了，find函数的实现是：

首先找节点x的根节点root，再基于x进行向上的路径压缩。

这其实完全可以合为一个操作，用到了递归，效率相当高：

int find(int x){   //不但完成了根节点查找，还完成了路径压缩操作
    if(x!=pre[x])
        pre[x] = find(pre[x]);
    return pre[x];
}

OVER

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网