## Java實現并查集 ~~~ /** * 并查集 * @Author: mango * @Date: 2022/5/22 4:57 下午 */ public class UnionFindSet<V> { // 原始數據對應的節點集合map private Map<V,Node<V>> dataMap; // 頂層頭節點所在的集合大小map private Map<Node<V>,Integer> countMap; /** * 節點 * @param <V> 原始數據 */ private final class Node<V>{ public V val; // 前指針 public Node<V> pre; public Node(V val) { this.val = val; } @Override public String toString() { return "Node{" + "val=" + val + ", pre.val=" + pre.val + '}'; } } public UnionFindSet(List<V> vList){ dataMap = new HashMap<>(); countMap = new HashMap<>(); for(V v : vList){ Node<V> node = new Node<>(v); node.pre = node; dataMap.put(v,node); countMap.put(node,1); } } /** * 判斷2個元素是否在同一個集合 * 找2個頭節點，如果頭節點相同則說明是同一個集合 * @param a * @param b * @return */ public boolean isSameSet(V a, V b){ return getHead(dataMap.get(a)) == getHead(dataMap.get(b)); } /** * 合并2個元素所在的節點到同一個集合 * 如果是同一個集合，就跳過 * 找到2個元素的頭節點，將小的集合的頭節點指向大的集合的頭節點 * 合并后，將原來的節點所在集合數據刪除 * @param a * @param b */ public void union(V a, V b){ if(isSameSet(a, b)){ return ; } Node<V> aHead = getHead(dataMap.get(a)); Node<V> bHead = getHead(dataMap.get(b)); Integer aCount = countMap.get(aHead); Integer bCount = countMap.get(bHead); Node<V> bigHead = aCount >= bCount ? aHead : bHead; Node<V> smallHead = bigHead == aHead ? bHead : aHead; smallHead.pre = bigHead; countMap.put(bigHead,aCount + bCount); countMap.remove(smallHead); } /** * 通過節點向上找頭節點 * 利用棧來優化節點指向關系為扁平化，加快查詢效率為O(1) * @param node * @return */ private Node<V> getHead(Node<V> node){ // 使用棧將底層節點都入棧 Stack<Node<V>> speed = new Stack<>(); while (!node.val.equals(node.pre.val)){ node = node.pre; speed.push(node); } // 底層節點出棧，將pre指向head的node節點 while (!speed.isEmpty()){ speed.pop().pre = node; } return node; } @Override public String toString() { return "UnionFindSet{" + "dataMap=" + dataMap + ", countMap=" + countMap + '}'; } } ~~~