Java实现并查集
本文实例为大家分享了Java实现并查集的具体代码,供大家参考,具体内容如下
自下而上的树结构
接口
/** *@authorNino */ publicinterfaceUF{ intsize(); /** *看两个元素是否相连 *@paramp *@paramq *@return */ booleanisConnected(intp,intq); /** *将两个元素合并在一起,变成一个集合中的元素 *@paramp *@paramq */ voidunionElements(intp,intq); }
使用路径压缩的并查集
/** *@authorNino */ publicclassUnionFind5implementsUF{ privateint[]parent; //rank[i]表示以i为根的集合中树的层数 privateint[]rank; publicUnionFind5(intsize){ parent=newint[size]; rank=newint[size]; for(inti=0;i=parent.length){ thrownewIllegalArgumentException("pisillegal"); } if(p!=parent[p]){ parent[p]=find(parent[p]); } returnparent[p]; } /** *查询p,q是否同属一个集合 *时间复杂度O(h) *@paramp *@paramq *@return */ @Override publicbooleanisConnected(intp,intq){ returnfind(p)==find(q); } /** *合并元素p,q所属的集合,只需要把Rank低的根节点指向Rank高的根节点就可以 *O(h)复杂度 *@paramp *@paramq */ @Override publicvoidunionElements(intp,intq){ intpRoot=find(p); intqRoot=find(q); if(pRoot==qRoot){ return; } //败者食尘 if(rank[pRoot] 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。