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]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。