并查集接口：
public interface UF {
int getSize();
boolean isConnected(int p,int q);
void unionElements(int p,int q);
}public class UnionFind1 implements UF{
//存储相应元素的集合编号
private int[] id;
public UnionFind1(int size){
id=new int[size];
for(int i=0;i<id.length;i++){
id[i]=i;
}
}
@Override
public int getSize() {
return id.length;
}
//元素属于同一个集合，则这两个元素就是相连的
//时间复杂度：O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p)==find(q);
}
//查找p元素所属的集合
private int find(int p){
if(p<0 || p>=id.length){
throw new IllegalArgumentException("p is out of bound");
}
return id[p];
}
//时间复杂度：O(n)
@Override
public void unionElements(int p, int q) {
int pId=find(p);
int qId=find(q);
if(pId==qId){
return;
}
//连接两个元素后，如果它们是在两个不同的集合中，
//则现在由于p、q的连接，就会成为一个集合
for(int i=0;i<id.length;i++){
if(id[i]==pId){
id[i]=qId;
}
}
}
}
初始化并查集，每个节点指向自身，构成了森林。
union(4,3)，就是将4的父指针指向3，也就是说，此时3是4的父节点
...
uinon(9,4)，就是将9的父指针指向4所在集合的根节点
public class UnionFind2 implements UF{
//parent[i]表示i所指向的父节点
private int[] parent;
public UnionFind2(int size){
parent=new int[size];
//初始化时，将每个元素看成一个树节点，它们指向自身，构成森林
for(int i=0;i<parent.length;i++){
parent[i]=i;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找p元素所在的树（也就是集合）的根节点
//时间复杂度：O(h),其中h为该集合树的深度
private int find(int p){
if(p<0 || p>=parent.length){
throw new IllegalArgumentException("p is out of bound.");
}
while(p!=parent[p]){
p=parent[p];
}
//返回的是p所在的集合的编号，同时也是p集合非根节点
return p;
}
@Override
public boolean isConnected(int p, int q) {
//根节点相同，就是同一个集合
return find(p)==find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if(pRoot==qRoot){
return;
}
//将p所在集合的根节点指向q所在集合的根节点
parent[pRoot]=qRoot;
}
}- 对UinonFind2的改进：
根据两个元素所在的集合的元素个数的不同，判断合并方向。 将元素少的集合合并到元素多的集合上，降低树的高度。
public class UnionFind3 implements UF{
//parent[i]表示i所指向的父节点
private int[] parent;
//sz[i]表示i元素所在的集合的元素个数
private int[] sz;
public UnionFind3(int size){
parent=new int[size];
sz=new int[size];
//初始化时，将每个元素看成一个树节点，它们指向自身，构成森林
for(int i=0;i<parent.length;i++){
parent[i]=i;
//初始化时，每个节点就是一个集合，那么元素个数就是1
sz[i]=1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找p元素所在的树（也就是集合）的根节点
//时间复杂度：O(h),其中h为该集合树的深度
private int find(int p){
if(p<0 || p>=parent.length){
throw new IllegalArgumentException("p is out of bound.");
}
while(p!=parent[p]){
p=parent[p];
}
//返回的是p所在的集合的编号，同时也是p集合非根节点
return p;
}
@Override
public boolean isConnected(int p, int q) {
//根节点相同，就是同一个集合
return find(p)==find(q);
}
//根据两个元素所在的集合的元素个数的不同，判断合并方向。
//将元素少的集合合并到元素多的集合上，降低树的高度。
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if(pRoot==qRoot){
return;
}
//将p所在集合的根节点指向q所在集合的根节点
//parent[pRoot]=qRoot;
//改进：
if(sz[pRoot]<sz[qRoot]){
//p节点所在的集合元素较少，pRoot的父指针指向qRoot
parent[pRoot]=qRoot;
sz[qRoot]+=sz[pRoot];
}else{
parent[qRoot]=pRoot;
sz[pRoot]+=sz[qRoot];
}
}
}对于如下并查集，unoin(4,2)
按照“基于size的优化"将8指向7，此时树的深度增加了。
我们应该是这样合并合理：将7指向8，树的深度没有增加，效率更高
- 基于rank的优化：rank[i]表示根节点为i的树的深度
根据两个元素所在的集合的树的深度不同，判断合并方向。 将深度浅的集合合并到深度深的的集合上，降低树的高度。
public class UnionFind4 implements UF{
//parent[i]表示i所指向的父节点
private int[] parent;
//rank[i]表示根节点为i的树的深度
private int[] rank;
public UnionFind4(int size){
parent=new int[size];
rank=new int[size];
//初始化时，将每个元素看成一个树节点，它们指向自身，构成森林
for(int i=0;i<parent.length;i++){
parent[i]=i;
//初始化时，每个节点就是一个集合，那么元素所在集合的深度就是1
rank[i]=1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找p元素所在的树（也就是集合）的根节点
//时间复杂度：O(h),其中h为该集合树的深度
private int find(int p){
if(p<0 || p>=parent.length){
throw new IllegalArgumentException("p is out of bound.");
}
while(p!=parent[p]){
p=parent[p];
}
//返回的是p所在的集合的编号，同时也是p集合非根节点
return p;
}
@Override
public boolean isConnected(int p, int q) {
//根节点相同，就是同一个集合
return find(p)==find(q);
}
//根据两个元素所在的集合的树的深度不同，判断合并方向。
//将深度浅的集合合并到深度深的的集合上，降低树的高度。
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if(pRoot==qRoot){
return;
}
//将p所在集合的根节点指向q所在集合的根节点
//parent[pRoot]=qRoot;
/*改进：
if(sz[pRoot]<sz[qRoot]){
//p节点所在的集合元素较少，pRoot的父指针指向qRoot
parent[pRoot]=qRoot;
sz[qRoot]+=sz[pRoot];
}else{
parent[qRoot]=pRoot;
sz[pRoot]+=sz[qRoot];
}*/
//改进
if(rank[pRoot]<rank[qRoot]){
//pRoot集合的深度浅，pRoot的父指针指向qRoot
parent[pRoot]=qRoot;
}else if(rank[pRoot]>rank[qRoot]){
parent[qRoot]=pRoot;
}else{ //rank[pRoot]==rank[qRoot]
parent[pRoot]=qRoot;
//pRoot的父指针指向qRoot,则qRoot所在的集合深度+1
rank[qRoot]+=1;
}
}
}前面的 UnionFind4的find(4)，算法过程：
路径压缩后，算法过程：
//查找p元素所在的树（也就是集合）的根节点
//时间复杂度：O(h),其中h为该集合树的深度
private int find(int p){
if(p<0 || p>=parent.length){
throw new IllegalArgumentException("p is out of bound.");
}
while(p!=parent[p]){
parent[p]=parent[parent[p]];
p=parent[p];
}
//返回的是p所在的集合的编号，同时也是p集合非根节点
return p;
}
//查找p元素所在的树（也就是集合）的根节点
//时间复杂度：O(h),其中h为该集合树的深度
private int find(int p){
if(p<0 || p>=parent.length){
throw new IllegalArgumentException("p is out of bound.");
}
if(p!=parent[p]){
parent[p]=find(parent[p]);
}
return parent[p];
}