并查集 #

一维并查集 #

一维并查集需要初始化两个数组，初始化一个容量信息。

parent数组，用于存放每一个节点的祖先信息。并且使用路径压缩信息，每一个元素都是直接存放其祖先
rank数组，用于标识每一棵树的高度，将小高度的树合并到大高度的树上，降低树的高度

class UnionFind{
  int[] parent;
  int[] rank;
  public UnionFind(int size){
		parent=new int[size];
    rank=new int[size];
    for(int i=0;i<size;i++){
			parent[i]=i;// 初始化每一个节点的祖先都是自己
      rank[i]=0; // 其实默认也是0
    }
  }
  public int find(int x){
    if(parent[x]!=x){
      parent[x]=find(parent[x]);
    }
    return parent[x];
  }
  public void union(int x,int y){
		int rootX=find(x);
    int rootY=find(y);
    if(rootX!=rootY){
      if(rank[rootX]<rank[rootY]){
          parent[rootX]=rootY;
      }else if(rank[rootX]>rank[rootY]){
          parent[rootY]=rootX;
      }else{
        parent[rootX]=rootY;
        rank[rootY]++; // Increment rank of rootY to maintain balance when ranks are equal
      }
    }
  }
}