# 并查集 ## 定義 并查集是一種樹型的數據結構，用于處理一些不相交集合的合并及查詢問題。 并查集的思想是用一個數組表示了整片森林（parent），樹的根節點唯一標識了一個集合，我們只要找到了某個元素的的樹根，就能確定它在哪個集合里。 ## 一張圖快速入門 1. 先將普通節點初始化為并查集，每一個集合內都只有自己 2. 當2個節點要合并時，先判斷是不是在同一個集合中，如果是則跳過，不是則合并 3. 合并的時候，先找到要合并節點的頭節點，再將小數量集合的頭節點指向大數量集合的頭節點。 4. 在獲取頭節點的時候做偏平化處理，加快下次找頭節點的過程  ## java實現并查集 [Java實現并查集](Java%E5%AE%9E%E7%8E%B0%E5%B9%B6%E6%9F%A5%E9%9B%86.md) ## 測試 ~~~ public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); list.add("E"); UnionFindSet<String> unionFindSet = new UnionFindSet<>(list); unionFindSet.union("A","B"); unionFindSet.union("C","D"); System.out.println(unionFindSet); unionFindSet.union("E","B"); System.out.println(unionFindSet); unionFindSet.union("C","E"); System.out.println(unionFindSet); } ~~~ 輸出：（和上圖例子步驟保持一致） ``` UnionFindSet{dataMap={A=Node{val=A, pre.val=A}, B=Node{val=B, pre.val=A}, C=Node{val=C, pre.val=C}, D=Node{val=D, pre.val=C}, E=Node{val=E, pre.val=E}}, countMap={Node{val=E, pre.val=E}=1, Node{val=A, pre.val=A}=2, Node{val=C, pre.val=C}=2}} UnionFindSet{dataMap={A=Node{val=A, pre.val=A}, B=Node{val=B, pre.val=A}, C=Node{val=C, pre.val=C}, D=Node{val=D, pre.val=C}, E=Node{val=E, pre.val=A}}, countMap={Node{val=A, pre.val=A}=3, Node{val=C, pre.val=C}=2}} UnionFindSet{dataMap={A=Node{val=A, pre.val=A}, B=Node{val=B, pre.val=A}, C=Node{val=C, pre.val=A}, D=Node{val=D, pre.val=C}, E=Node{val=E, pre.val=A}}, countMap={Node{val=A, pre.val=A}=5}} ```