Java實現並查集

本文實例為大家分享了Java實現並查集的具體代碼，供大家參考，具體內容如下

自下而上的樹結構

接口

  /**   * @author Nino   */  public interface UF {   int size();     /**    * 看兩個元素是否相連    * @param p    * @param q    * @return    */   boolean isConnected(int p, int q);     /**    * 將兩個元素合併在一起，變成一個集合中的元素    * @param p    * @param q    */   void unionElements(int p, int q);  }

使用路徑壓縮的並查集

  /**   * @author Nino   */  public class UnionFind5 implements UF {   private int[] parent;   //rank[i]表示以i為根的集合中樹的層數   private int[] rank;     public UnionFind5(int size) {    parent = new int[size];    rank = new int[size];    for (int i = 0; i < size; i++) {     parent[i] = i;     rank[i] = 1;    }   }     @Override   public int size() {    return parent.length;   }     /**    * 查找過程，查找元素p所對應的集合編號    * O(h)複雜度，h為樹的高度    * 使用路徑壓縮    * @param p    * @return    */   private int find(int p) {    if (p < 0 && p >= parent.length) {     throw new IllegalArgumentException("p is illegal");    }    if (p != parent[p]) {     parent[p] = find(parent[p]);    }    return parent[p];   }     /**    * 查詢p, q是否同屬一個集合    * 時間複雜度O(h)    * @param p    * @param q    * @return    */   @Override   public boolean isConnected(int p, int q) {    return find(p) == find(q);   }     /**    * 合併元素p, q所屬的集合，只需要把Rank低的根節點指向Rank高的根節點就可以    * O(h)複雜度    * @param p    * @param q    */   @Override   public void unionElements(int p, int q) {    int pRoot = find(p);    int qRoot = find(q);      if (pRoot == qRoot) {     return;    }    //敗者食塵    if (rank[pRoot] < rank[qRoot]) {     parent[pRoot] = qRoot;    } else if (rank[qRoot] < rank[pRoot]) {     parent[qRoot] = pRoot;    } else {     parent[qRoot] = pRoot;     rank[pRoot] += 1;    }   }  }