欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-24 14:37:03
之前在CSDN看到一篇很受欢迎的讲解并查集的博文,其中自然用到了路径压缩: 你也许会发现问题了,find函数的实现是: 首先找节点x的根节点root,再基于x进行向上的路径压缩。 这其实完全可以合为一个操作,用到了递归,效率相当高: OVER ......

之前在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