# 並查集 Disjoint set union --- 試想一個情境 今天是開學第一天 而你完全不認識其他的同學 其他的同學也是 他們也完全不認識其他的人 隨著你們越混越熟 這樣你勢必會認識一些人 只要你認識一個同學 你也會跟他的朋友們混在一起 只要你跟一個人有關係 那怕是$(朋友的)^n$都算跟你混一起的 ---- 總共有$N$個同學 有$Q$次操作 ($1\le N,Q\le 10^5$) 操作有兩種 - 問 $x$ 與 $y$ 目前是不是好朋友 - $x$ 同學跟 $y$ 同學變成好朋友了 ---- ### 想法1:DFS 啊這不就 DFS? 每次要問的時候從 $x$ 同學 DFS 看走不走的到 $y$ 啊 ---- 事情往往不是那麼的簡單 DFS 一次的複雜度為 $O(NQ)$ 在剛剛設定的數值範圍下這樣的複雜度是過不了的 ---- ### 想法2:DSU 試想每個同學記錄一個"父節點" $P_i$ 也就是說在兩兩合併時抓其中一個同學當另一個同學的父節點 那要確認倆倆是否在同一團時 一直往上爬爬到最高的那個節點 如果兩個人最高的祖先都一樣 那就表示兩個人在同一個團裡 [sample code](https://ideone.com/slR9PU) --- ## 複雜度討論 可是如果變成一條鍊了怎麼辦？ 複雜度一樣很噁心啊  ---- 確實 如果併到最後你太衰變成一條鍊 那這樣的搜索速度會是 $O(N)$ 複雜度還是 $O(NQ)$ ---- ### 啟發式合併 ---- 維護一個 $sz[i]$ 表示這個點為根的那團有幾個人 那要併兩個團的時候 我們讓 $sz$ 比較小的去接到另一團 ----  ---- 因為每次從一個點往下時 剩下的節點數必定小於原來的$\frac{1}{2}$ 這樣樹高就會是$\log {N}$ ```cpp= void join(int a,int b){ a=find(a); b=find(b); if(a==b) return; if(num[a]<num[b]) swap(a,b); p[b]=a; num[a]+=num[b]; } ``` ---- ### 路徑壓縮 ---- 這個神奇的東西可以加速到近乎常數的搜索 ---- 每次都要從一個點爬到樹根 不覺得有點麻煩? ---- 為何不每次爬到樹根的時候 把這一路上經過的點的 $P_i$ 都改成樹根? ---- 這樣一來樹的高度就不會太高 均攤下來查找的複雜度會是 $O(\alpha(N))$ 在 $N\le10^9$ 時 $\alpha(N)$ 不會超過5 ```cpp= int find(int node){ return node==p[node]?node:p[node]=find(p[node]); } ``` ---- 在實作時 其實只要啟發式合併或路徑壓縮選一個 就可以達到 $O(nlog(n))$ 的複雜度了 所以如果你懶 + 時限允許的話可以不用每次兩個都寫 --- [Usaco Gold MooTube](http://www.usaco.org/index.php?page=viewproblem2&cpid=789) 有一顆 $N$ 個點的樹，並且有邊權 有 $Q$ 次詢問 - 給 $v,k$ 問從 $v$ 開始只走邊權 $\leq k$ 的邊可以走到多少點？ ---- 將邊權由小排到大 並且先將所有詢問讀進來，依照 $k$ 由小排到大 ---- 並且維護一個雙指針 如果這次的詢問為 $k_i$ 則將邊權 $\leq k$ 的邊都加入一個並查集 則這個詢問的答案就是 $v$ 所在的團的大小！ ---- [sample code](https://ideone.com/odwkNG) --- 謝謝大家