union-find

用途 判斷2個目標是否在同一組、判斷2個目標是否相連 實現 用1維陣列表示N個目標 array[n]表示第n個目標的父節點 每個群組可視為一棵樹，任意2點有相同根節點表示同組 array[i]==i表示到達根節點 將2點設為同組只需 public void unite(int p, int q) { int i = root(p); int j = root(q); id[i] = j; } 瓶頸 樹太深時尋找根節點費時 優化 另外開個陣列紀錄群組大小，合併時將小樹放到大樹下，減少深度 在訪問根的過程中，將所有節點的父節點都順手改為父父節點，減少深度 參考資料 https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

編程作業: Percolation 100分關鍵在使用2個WeightedQuickUnionUF，一個繪圖用，一個判斷滲透用 Percolation.java import edu.princeton.cs.algs4.WeightedQuickUnionUF; public class Percolation { private static final int FULL_ROOT = 0; private final int n; private final boolean[] open; private final WeightedQuickUnionUF uf; private final WeightedQuickUnionUF ufForCheckPercolates; private final int END_ROOT; private int openSize; private boolean percolates; public Percolation(int n) { if (n <= 0) throw new java.lang.IllegalArgumentException(); this.n = n; final int size = n * n + 2; this.open = new boolean[size]; this.