--- tags: 109_FDCS --- # Disjoint Set Union (DSU) / 互斥集 DSU是用來快速判斷兩個點是否屬於同一個集合的資料結構 資料結構的模型是很多棵樹，如果兩個點的樹根不同則兩個點不是屬於同一棵樹 藉此來判斷是否屬於同一個集合 ## init 對於每一個點，DSU要維護兩個值 1. 子樹大小 2. 父節點 ```cpp=1 vector<int> anc(n), sz(n, 1); iota(anc.begin(), anc.end(), 0); ``` 而一開始所有點的子樹大小都為 $1$ 父節點都為自己 **只要父節點為自己，則此節點為樹根** ## find 用來找根節點的函式 ```cpp=3 auto find = [&anc](int a) { if(anc[a] == a) return a; else return find(anc[a]); } ``` 但是這會產生一個問題，每次詢問最差會跑到 $O(n)$ 所以必須做一些改進 ## find (fixed) 可以發現對於誰是誰的孩子、誰是誰的父親其實不重要 **重要的只有根節點是誰**，所以能盡量往上指就往上指 在往上遞迴的過程中，可以將經過的所有點的父節點全部都指向根節點 這樣下次詢問就可以降成 $O(1)$ 這種手法叫做**路徑壓縮** ```cpp=3 auto find = [&anc](int a) { if(anc[a] == a) return a; else return anc[a] = find(anc[a]); } ``` 或者我們常常壓成一行 ```cpp=3 auto find = [&anc](int a) { return anc[a] == a ? a : anc[a] = find(anc[a]); } ``` ## join 用來把兩個點所屬的集合合併 ```cpp= auto join = [&anc, &find](int a, int b) { if(find(a) == find(b)) return false; anc[find(a)] = find(b); return true; } ``` 這樣就完成最簡單的合併了，而通常這樣就夠快了 不過可能有些人注意到了，`sz`根本沒用到阿 度，因為接下來的優化才會用到它 ## join (fixed) 我們在合併時，會希望每個點到根節點的距離越短越好 所以比較小的集合的根節點應該指向大集合的根節點，才能有效降低期望距離 這種手法稱為**啟發式合併** i.e. ```cpp= auto join = [&anc, &sz, &find](int a, int b) { if(find(a) == find(b)) return false; if(sz[find(a)] < sz[find(b)]) sz[find(b)] += sz[find(a)], anc[find(a)] = find(b); else sz[find(a)] += sz[find(b)], anc[find(b)] = find(a); return true; } ```