<style> .reveal .slides { text-align: left; font-size:35px } </style> # pretrain 3 Introduction to Competitive Programming 12/15 ---- * Disjoint Set(Union-Find) * Minimum Spanning Tree (kruskal) --- ## Disjoint Set (Union-Find) (DSU) 並查集，又稱不相交集資料結構 ---- 並查集是一種樹狀結構 <!-- 大概說一下樹是什麼 --> 處理集合問題，主要有以下兩個操作 * 查詢元素所在集合(find) * 合併兩個集合(union) ---- 並查集只需要用一個長度為 $n$ 的陣列即可， 陣列內第 $i$ 格存的值為第 $i$ 個節點的父節點編號 ```cpp= int f[n]; f[3] // 節點 3 的父節點編號 f[5] // 節點 5 的父節點編號 ``` ---- ### 根節點 如果一個點為根節點，他的父節點為自己 (f[x] == x) 以下圖為例， 1、6 為根節點  ---- ## find 函數 find 函數會找到某個節點 x 的根節點 如果兩個點的根節點相同，則所屬同一個集合 i.e. find(x) == find(y), 則 x 與 y 所屬同一個集合 ---- ## find 函數 ```cpp= int find(int x){ if ( x == f[x] ) // 如果當前節點為 f[x]==x return x; // 則為根節點 return find(f[x]); } ``` ---- ## union 函數 <div style="font-size:30px"> 如果有兩個節點 a, b 所在的集合想要合併成一個集合 <br> 則做法為找到兩集合的根節點 <br> 將其中一個集合的根節點連到另外一個的根節點 <br> <div> 以下圖為例  ---- ## union 函數 <div style="font-size:30px"> 合併 2 所在的的集合 跟 7 所在的集合 <br> 則先找到 2 的根節點 =1, 7 的根節點 =6 <br> 將其中一個根節點的父節點設為另一個根節點 <br> </div>  <div style="font-size:30px"> 則 7 所在的集合所有元素的根節點都會變成 1 </div> ---- ## union 函數 <div style="font-size:30px"> 這邊合併的函數名稱不使用 union <br> 因為 union 為關鍵字 (撞名內建函數） <br> 因此名稱改用 merge </div> ```cpp= void merge(int x,int y) // 合併 x, y 所在集合 { x = find(x); // x 找到其根節點 y = find(y); // y 找到其根節點 if(x != y) // 如果 x,y 原本就屬於同一個集合則不需合併 f[y]=x; // 將其中一個根節點連到另一個 } ``` ---- ## 初始化 一開始每個元素皆屬於屬於不同集合 因此會將節點指向自己，因為這時候每個元素都是根節點 ```cpp= int f[N]; void init(){ for(int i=0;i<n;i++) f[i] = i; // 將每個元素根節點設為自己 } ``` <!-- --> ---- ## 完整程式 ```cpp= void init(){ for(int i=0;i<n;i++) f[i]=i; } int find(int x){ if ( x == f[x] ) // 如果當前節點為 f[x]==x return x; // 則為根節點 return find(f[x]); } void merge(int x,int y){ x=find(x),y=find(y); if(x!=y) f[y]=x; } ``` <!-- --> ---- ## 優化 在最差的情況下 長出來的樹有可能會變成一條鏈 $\rightarrow$ 每次操作複雜度退化成 $O(N)$  ---- ## 啟發式合併 記錄每棵樹的大小，並在每次合併的時候，將小的集合合併到大的集合。 ---- ### 做法 使用 sz[] 紀錄每個節點的為根的集合大小 ```cpp= int f[N], sz[N]; void merge(int x, int y) { x = find(x), y = find(y); if(x==y) return; if(sz[x] < sz[y]) swap(x, y); // 將 x 變成大的 sz[x] += sz[y]; // 加上去 f[y] = x; } ``` <!-- --> 在初始化的時候將每個集合大小 sz[i] 都設成 1 ---- ### 分析 如果是原本的做法 假設有 $n$ 個節點，合併 $n - 1$ 次 每次合併都由大小為 $i$ 的合併到大小為 $1$ 的，樹就會長成最差的情況（鏈） 每次查詢會退化到 $O(n)$  ---- ### 分析 而通過啟發式合併，可以發現如果將大的樹接在小的樹，會讓樹的深度 + 1，反過來深度還是一樣。  ---- ## 路徑壓縮 在每次 find() 的時候 把經過節點的父節點 全部設成根節點 ```cpp= int find(int x){ if(f[x] == x) return x; f[x] = find(f[x]); // 直接將 x 的父節點設成根節點 return f[x]; } ``` <!--可以再模擬一下 f[x] = find(f[x]) 的地方 --> ---- <div style="font-size:30px"> 呼叫 find(5) 會經過節點 5 4 3 2 1 <br> 將中間每個節點的父節點直接設為根節點 </div> ```cpp= find(5) ``` <div style="position: absolute; right: 70%; top:100%;">  </div> <div style="position: absolute; right: 60%; top:200%;"> $\rightarrow$ </div> <div style="position: absolute; right: 10%; top:150%;">  </div> ---- 此時每筆操作複雜度降到 $O(\alpha(N))$ $O(\alpha(N))$ 趨近於 $O(1)$ $\alpha( 2^{2^{10^{19729}}} ) = 5$ 因此並查集複雜度 幾乎是常數時間 ---- ## 完整程式 ```cpp= int f[N], sz[N]; void init(){ for(int i=0;i<n;i++) { f[i] = i; sz[i] = 1; } } int find(int x){ if ( x == f[x] ) // 如果當前節點為 f[x]==x return x; // 則為根節點 f[x] = find(f[x]); return find(f[x]); // } void merge(int x, int y) { x = find(x), y = find(y); if(x==y) return; if(sz[x] < sz[y]) swap(x, y); // 將 x 變成大的 sz[x] += sz[y]; f[y] = x; } ``` <!-- --> --- ## 並查集應用 ---- ### Almost-union-find 題序：一個有三種操作的並查集 1. Union(x, y): 把 x , y 加入同一集合 2. Move(x, y): 將 x 移動到 y 集合 3. Return(x):將 x 所在的集合總和與元素個數回傳 - $1\le n, m\le 10^5$ ---- 可以發現操作 1、3 都是正常的並查集操作 只需要在 merge 的時候維護總和跟大小 只有操作 2 比較不一樣，需要做到刪除的操作。 ---- 我們可以從兩種情況來看刪除 1. 移除的是葉節點 2. 移除的不是葉節點 ---- ### 1. 移除的是葉節點 在這個情況下，我們只要將根節點記錄大小跟總和的變數把這個節點減掉即可。 ---- ### 2. 移除的不是葉節點 感覺很麻煩，我也不會 因此我們需要讓需要被移除的節點都變成葉節點 再額外新增一個節點，讓所有節點一開始都是葉節點，並在 merge 後及 move 後也還是葉節點。 ---- 通過新增一個虛擬的點，並在一開始將點連過去，就可以讓所有節點一開始都是葉節點了！ ```cpp= int f[N], int sz[N], int sum[N]; void init(int n) { //有 n 個點 for(int i = 0; i < n; i++) { f[i] = n + i; f[n + i] = n + i; sz[i] = 1; sz[n + i] = 1; sum[i] = i; sum[n + i] = i; } } ``` <!-- --> 至於 find、merge 如何實作，就留給大家了 這題也是今天的題單練習之一。 ---- ## 例題 題序：給一張 $n$ 個點、$m$ 條邊的圖， <!-- 講圖是什麼--> 要做 $q$ 次操作，每次將一條邊拔掉 詢問每次拔掉後還有多少塊連通塊？<!-- 這邊要解釋什麼是連通塊--> 範圍： $n, m, q\le 10^6$ <!-- 不確定範圍要多少 --> ---- ### 做法 每次刪除後看有幾個連通塊需要花 $O(n + m)$ 的時間 而我們有 $q$ 次詢問，很明顯不能這樣做 那這題要怎麼用並查集維護連通塊呢？ ---- ### 做法 找有幾個連通塊的 code ```cpp= struct edge{ int x, y; } edge E[M]; int vis[N] = {0}; for(int i = 0 ;i < m; i++) { merge(E[i].x, E[i].y); } for(int i = 0; i < n; i++) { vis[find(i)] = 1; } int sum = 0; for(int i = 0; i < n; i++) { if(vis[i] == 1) { sum++; } } ``` <!-- --> ---- ### 做法 如果將刪除變成合併，就可以用到並查集了 因此我們可以將操作反過來做 先將需要刪除的邊刪除，並花 $O(n)$ 時間計算現在有多少連通塊 然後將指令從後往前做，可以發現這樣子操作就從刪除變成合併了！ 複雜度 $O(n + m + q)$ --- 休息時間 這邊有隊伍的表單喔 :) https://docs.google.com/forms/d/11ttYBH-9L9EIylsBPU3tLiBAwG6sckADLvGAO_lDvlY/edit?pli=1  --- ## 最小生成樹 :evergreen_tree: 「生成樹」。從一張圖取出一棵樹，包含圖上所有點。可能有許多種。 而最小生成樹是其中所有的生成樹中，權重總和最小的。 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- ## Kruskal' algorithm greedy method , 將所有邊照權重大小排序，從權重小的邊開始窮舉，依序窮舉到大， 當邊兩側的節點原本不連通就加邊，否則就捨棄這條邊 這個做法是對的，但為什麼是對的 🤔 ---- ## 證明 生成樹的一個性質： > 對於兩個生成樹 $T_1$ 與 $T_2$ 和一條邊 $e \in T_1 \backslash T_2$ > 存在 $e_2 \in T_2 \backslash T_1$ 使得 $(T_2\backslash \{e_2\})\cup \{e_1\}$ 依然是生成樹。 從 $T_1$ 拿出一條邊加入 $T_2$ 後，$T_2$ 會形成一個環，此時移除環上任一邊即可讓 $T_2$ 有 $n-1$ 條邊連通，這個時候 $T_2$ 也還會是一棵樹。 ---- Kruskal' algorithm 的證明： 令Kruskal演算法找到的生成樹為 $T$，而最小生成樹為 $T^*$ 如果有多個最佳解，令 $T^*$ 為與 $T$ 交集最大的一個。 如果 $T=T^*$ 就結束了，否則，令 $e_i$ 是只出現在 $T$ 的邊且編號最小 根據上面的性質，存在 $e_j \in T^* \backslash T$ 使得 $T^*$ 把 $e_j$ 換出去再把 $e_i$ 放進來仍是一棵生成樹。 ---- 假如 $i < j$，那 $e_i$ 的權重 $\leq e_j$ 的權重。但由於$T^*$是最小生成樹，這樣做出來的 $T$ 的權重會跟 $T^*$ 一樣(或更小)，但是與$T$的交集比 $T^*$ 大，矛盾。 假如 $i > j$，由於比 $j$ 前面的邊都在 $T$ 與 $T^*$ 中，根據 Kruskal 演算法的特性，在遇到 $e_j$ 時就會把 $e_j$ 加入 $T$ 中了，矛盾。 故得證 $T=T^*$ ---- <div style="background-color:white">  </div> ---- ## 加入邊 使用並查集，一開始所有點都沒連任何邊 因此所有點都屬於自己的集合 當兩個點有連邊，代表他們屬於同一個集合 因此可以用並查集判斷，判斷是否已經為同一個集合 ---- ## 結構 使用 struct 儲存邊 (邊的兩個端點 u, v、權重 w) 多載 < 小於運算子，使用邊權重比較兩條邊的大小關係 ```cpp= struct Edge{ int u, v, w; // 點 u 連到點 v 並且邊權為 w bool operator<(const Edge& rhs){ return w < rhs.w; //兩條邊比較大小用邊權比較 } }; Edge graph[200005]; // 宣告 Edge 型態的陣列 graph ``` ---- ## 程式碼 將邊照大小依序嘗試加入圖中， 如果邊的兩點未連通，則連通兩點 ```cpp= sort(graph,graph+m); // 將邊照大小排序 int ans=0; for(int i=0;i<m;i++){ //>:) if(find(graph[i].u) != find(graph[i].v)){ // 如果兩點未聯通 merge(graph[i].u,graph[i].v); // 將兩點設成同一個集合 ans += graph[i].w; // 權重加進答案 if(sz[find(graph[i].u)]==n) break; //當並查集大小等價於樹內點的數量 } } cout<<ans<<endl; ``` ---- ## 瓶頸生成樹 令 $T_i$ 是這張圖的所有生成樹，會有樹 $T^*$ 它的最大邊權值為所有 $T_i$ 的最小 性質: 最小生成樹是瓶頸生成樹的充分不必要條件。 即最小生成樹一定是瓶頸生成樹，而瓶頸生成樹不一定是最小生成樹。 ---- ## 複雜度分析 依照權重排序所有邊 $O(MlgM)$ 窮舉每條邊加入 $O(M\cdot \alpha (N))$ -> 總複雜度 $O(MlgM)$ --- ## Question Time and Practice