c++并查集优化(基于size和rank)
基于size的优化是指:当我们在指定由谁连接谁的时候,size数组维护的是当前集合中元素的个数,让数据少的指向数据多的集合中
基于rank的优化是指:当我们在指定由谁连接谁的时候,rank数组维护的是当前集合中树的高度,让高度低的集合指向高度高的集合
基于size的代码:UnionFind3.h
#ifndefUNION_FIND3_H_ #defineUNION_FIND3_H_ #include#include namespaceUF3 { classUnionFind { private: int*parent; int*sz;//sz[i]就表示以i为根的集合中元素的个数 intcount; public: UnionFind(intcount) { this->count=count; parent=newint[count]; sz=newint[count]; for(inti=0;i =0); while(p!=parent[p])//这个是写到find里面的 { p=parent[p]; } returnp; } voidunionElements(intp,intq) { intpRoot=find(p); intqRoot=find(q); if(pRoot==qRoot) return; if(sz[pRoot] 基于rank的代码:UnionFind4.h
#ifndefUNION_FIND4_H_ #defineUNION_FIND4_H_ #include#include namespaceUF4 { classUnionFind { private: int*parent; int*rank;//rank[i]就表示以i为根的集合的层数 intcount; public: UnionFind(intcount) { this->count=count; parent=newint[count]; rank=newint[count]; for(inti=0;i =0); while(p!=parent[p])//这个是写到find里面的 { p=parent[p]; } returnp; } voidunionElements(intp,intq) { intpRoot=find(p); intqRoot=find(q); if(pRoot==qRoot) return; if(rank[pRoot] rank[qRoot]) { parent[qRoot]=pRoot; } else { parent[pRoot]=qRoot;//这里谁指向谁无所谓 rank[qRoot]++; } } boolisConnected(intp,intq) { returnfind(p)==find(q); } }; }; #endif 剩下的头文件和main文件在上一个并查集的博客中有,就不再粘贴出来了
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。