关于并查集的路径压缩(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
下一篇: 老年哮喘的区别