<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Graph Introduction to Competitive Programming 2022/04/06 ---- - Topological Sort - Lowest Common Ancestor - Second Best Minimum Spanning Tree - LCA Euler Tour Technique - Euler Tour and Euler Circuit --- ## 拓撲排序 ### Topological Sort 給一張 DAG(有向無環圖)，求出一個順序使得排在後面的點走到時，所有有連到後面的點都排在前面 EX: 課程擋修規則(要先修過前面的基礎課程才能修進階課程) (求出修課順序)  以上圖為例，一個好的排序方法為 $4 \to 3 \to 1 \to 2 \to 6 \to 8 \to 7$ ---- ## 作法 可以使用 DFS/BFS，這邊講 BFS 的作法 觀察圖中，可以先放的點為沒有連到他的也就是入度為 0 的點(4、8)  放完之後把 4, 8 後，把 4, 8 連出去的邊移除  接著就看哪些點沒有入邊可以繼續做，直到每個點都放進去順序為止 ---- ## 實作 一開始建圖時，可以用一個陣列 deg[MXN] 紀錄每個點入度多少 ```cpp= for(int i=0;i<m;i++){ cin >> u >> v; //點 u 連到點 v edge[u].push_back(v); ++deg[v]; } ``` 建完圖之後，開始拔入度為0的點，可以用 queue 儲存要拔掉的點，依序拿出來 ```cpp= for(int i=0;i<n;i++){ if(!deg[i]) que.push(i); } ``` ---- ## 實作 每次從 queue 裡面取出一個點，再把有連到的點入度 -1 直到所有點都拔出來為止 ```cpp= for(int i:edge[u]){ --deg[i]; if(deg[i] == 0){ que.push(i); } } ``` ---- ## 複雜度 $O(N+M)$ 每個點都拔出來一次，拔掉的時候所有連出去的邊走過一遍 --- ## 最近共同祖先 ### Lowest Common Ancestor (LCA) 給定一顆有根樹，多筆詢問 每次給你兩個點 $u, v$，問同時為兩個點的祖先中，深度最深的點是誰 <div style="position: absolute; right: 10%;">  </div> 以右圖為例，根節點為1: 5 跟 6 的 lca 為 2 1 跟 7 的 lca 為 1 7 跟 8 的 lca 為 4 5 跟 4 的 lca 為 1 ---- ## 作法 定義 k 倍祖先為節點往根節點方向走 k 步的節點，超過根結點則設為根結點 ### 預處理 對於每個節點，儲存 $2^0、2^1、2^2...、2^{\lfloor lgN \rfloor }$倍祖先 <div style="position: absolute; right: 10%;">  </div> <div style="font-size:25px;position: absolute; right: 58%;"> | |$2^0$倍|$2^1$倍|$2^2$倍|$2^3$倍| | ------ | ---- | ---- | ---- | ---- | | node1 | 1 | 1 | 1 | 1 | | node2 | 1 | 1 | 1 | 1 | | node3 | 1 | 1 | 1 | 1 | | node4 | 3 | 1 | 1 | 1 | | ... | | | | | | node8 | 4 | 3 | 1 | 1 | </div> ---- ### 預處理 儲存每個節點 $2^0、2^1、2^2...、2^{\lfloor lgN \rfloor}$倍祖先 $2^0$ 倍祖先為父節點 $2^1$ 倍祖先為 $2^0$ 倍祖先的 $2^0$ 倍祖先 $2^2$ 倍祖先為 $2^1$ 倍祖先的 $2^1$ 倍祖先 ... $2^k$ 倍祖先為 $2^{k-1}$ 倍祖先的 $2^{k-1}$ 倍祖先 可以先 dfs 一遍，紀錄每個點的父節點( $2^0$ 倍祖先)是誰 而根節點的 $2^0$ 倍祖先為自己 ---- ### 預處理 $2^k$ 倍祖先為 $2^{k-1}$ 倍祖先的 $2^{k-1}$ 倍祖先 用 dfs 找到所有節點的 $2^0$ 倍祖先之後，即可計算出 $2^1$ 倍祖先 以此類推可以再算出 $2^2, 2^3, ..., 2^{\lfloor lgN \rfloor}$ 倍祖先 ```cpp= int anc[N][lgN+1]; for(int i=1;i<=lgN;i++){ for(int u=0;u<N;u++){ //點 u 的 2^i 倍祖先即為 u 的 2^(i-1) 倍祖先的 2^(i-1) 倍祖先 anc[u][i] = anc[anc[u][i-1]][i-1]; } } ``` $\lfloor lgN \rfloor$ 可以用C++ 內建函式 __lg(n) 求 ---- ## 時間戳記 紀錄每個點被走到以及離開的時間順序 如果其中兩點 $u, v$ 為祖先後代關係， 則祖先節點 $u$ 進去時間會早於後代 $v$，且離開時間會晚於後代  紀錄時間戳記即可判斷兩者是否為**祖先後代關係** 而可以在 dfs 時順便紀錄時間戳記 ---- ## 詢問 對於詢問兩點 $u, v$ 的最近共同祖先，可以分為三種 case: <div style="position: absolute; right: -5%;">  </div> 1. 點 $u$ 為點 $v$ 的祖先 2. 點 $v$ 為點 $u$ 的祖先 3. 兩者互不為彼此的祖先 前兩種 case 可以直接透過時間戳記判斷 並且答案即為祖先節點的那個 case1: lca(1, 7) = 1 case2: lca(6, 2) = 2 第三種 case 我們可以用 Binary Lifting Approach 得到答案 ---- ## Binary Lifting Approach 當點 $u, v$ 兩者互不為彼此的祖先的時候 若彼此都不是祖先關係，則我們找出 $u$ 的祖先中最靠近根節點的非 $v$ 的祖先 <div style="position: absolute; right: -5%;">  </div> 以點 $7, 2$ 為例，詢問兩點的 lca 我們先找到點 $7$ 往上不為點 $2$ 的點中最上面的 為點 $3$ 如果直接暴力找最差 $O(N)$ 而這時就用到剛剛建好的倍增祖先表 ---- ## Binary Lifting Approach 點 $u$ 往上移動，移動到不為點 $v$ 的祖先的點中最上面的那個 嘗試從移動到點 $u$ 的 $2^{\lfloor lgN \rfloor}$ 倍祖先，判斷是不是點 $v$ 的祖先，如果不是則移動上去 接著就 $2^{\lfloor lgN \rfloor -1},..., 2^1, 2^0$ 倍祖先嘗試移動 <div style="position: absolute; right: -15%;">  </div> 以點 $7, 2$ 為例 判斷節點 7 的 $2^3$ 倍祖先是否為點 2 的祖先(是) 判斷 $2^2$ 倍祖先是否為點 2 的祖先(是) 判斷 $2^1$ 倍祖先是否為點 2 的祖先(否) 則移動到 $2^1$ 倍祖先(節點3) 判斷 節點3 的 $2^0$ 倍祖先是否為點 2 的祖先(是) 最後找到節點 3，父節點(節點1)即為答案 ---- 如果我們要找的距離為 9，則可以透過 Binary Lifting Approach 往上移動 $2^3 + 2^0 = 9$ 最差情況為以下情況 query(8, 2) 從節點 8 往上跳到節點 3 (距離為 n-2)  ---- 紀錄 $2^0, 2^1, 2^2,..., 2^{\lfloor lgN \rfloor}$ 的所有倍數祖先 最差我們需要移動 N-2 步 $\sum\limits_{i=0}^{\lfloor lgN \rfloor} 2^i > N-2$ 因此一定可以走到 ---- ## 詢問 ```cpp= int getLca(int u, int v){ if(isAncestor(u, v)) return u; // 如果 u 為 v 的祖先則 lca 為 u if(isAncestor(v, u)) return v; // 如果 v 為 u 的祖先則 lca 為 u for(int i=lgN;i>=0;i--){ // 判斷 2^lgN, 2^(lgN-1),...2^1, 2^0 倍祖先 if(!isAncestor(anc[u][i], v)) // 如果 2^i 倍祖先不是 v 的祖先 u = anc[u][i]; // 則往上移動 } return anc[u][0]; // 回傳此點的父節點即為答案 } ``` ---- ## 複雜度 ### 預處理 每個節點建 $2^0$倍祖先，$2^1$倍祖先，$2^2$倍祖先，...，$2^{\lfloor lgN \rfloor}$倍祖先 總共$NlgN$個，每個建立為O(1) 複雜度為 $O(NlgN)$ ### 詢問 每筆詢問則是在樹上二分搜，找非共同祖先中最靠近根節點的節點 每次詢問最差$O(lgN)$ ### 總複雜度 $O(NlgN + QlgN)$ ---- ## 求樹上兩點的距離 多筆詢問，每次求樹上兩點 $(u, v)$的距離 <div style="position: absolute; right: -10%;">  </div> dist(5, 8) = 5 dist(7, 7) = 0 dist(6, 1) = 2 可以用倍增表 紀錄所有節點到 $2^0, 2^1,..., 2^{\lfloor lgN \rfloor}$ 倍祖先的距離 求出兩點的 lca 後，則 dist(u, v) = dist(u, lca) + dist(lca, v) 複雜度同求 LCA ---- 求出 LCA 後 若題目為求出樹上兩點間的資訊(如距離、路徑上最小/大值)等問題 都可以透過建立倍增表後，使用 Binary Lifting Approach 在複雜度 $O(NlgN + QlgN)$ 解決 ---- ## 次小生成樹 ### Second Best Minimum Spanning Tree 給你一張圖，請選出一些邊使得整張圖連通，並輸出次小的權重和。 $N, M \le 2 \cdot 10^5$  以上圖為例 最小生成樹為 1 + 2 + 4 = 7 次小為 1 + 3 + 4 = 8 ---- ## 作法 先求出 MST 之後，嘗試把每條不在 MST 上的邊放上去，而會形成環 把環上除了新的邊中權重最大的邊移除，判斷是否為答案  上圖綠色邊為MST上的邊，而我們可以嘗試把每條不在樹上的放上去 放 (1, 4) 形成環，把環上權重最大的移除 (1, 2) 權重為 7(原本的MST權重) + 3(新增的邊) - 2(環上權重最大的邊) = 8 放 (3, 4) 形成環，把環上權重最大的移除 (1, 3) 權重為 7(原本的MST權重) + 8(新增的邊) - 4(環上權重最大的邊) = 11 ---- ## 找出環上權重最大的邊 如果直接暴力找，複雜度 $O(MN)$ 因此有一個好的方法，使得找最大邊的複雜度降低 ---- ## LCA 如果對於 MST 去建 LCA 並且建出每個點到 $2^0, 2^1,...,2^{\lfloor lgN \rfloor}$ 倍祖先路徑上最大權重的邊 每次找環上權重最大的邊即為 max(點 $u$ 到 lca 路徑最大值, 點 $v$ 到 lca 路徑最大值)  每次只需要 $O(lgN)$ 即可找到環上最大權重! 複雜度 $O(NlgN + MlgN)$ --- ## 樹壓平 ### LCA and Euler Tour Technique <div style="font-size:25px"> 子樹詢問、修改 EX：有一棵樹$N (1\le N \le 2 \cdot 10^5)$個節點，節點上只會有$0,1$兩種點權， 兩種操作 1. 每次詢問某個點的子樹中有幾個1 2. 修改以某個點的子樹，將權重為0的改成1,1的改成0 </div> ---- 作法 $Q$ 筆詢問，每次 $O(N)$ 修改 複雜度 $O(QN)$ ...太慢了 因此我們要把樹壓平 ----  紀錄每個點dfs時進入的時間 node | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ---- | - | - | - | - | - | - | - | - | dfs time| 1 | 2 | 8 | 3 | 4 | 5 | 6 | 7 | ----  <div style="font-size:25px; text-align:left; margin-left:31%"> 而每個點的子樹，dfs順序必定會是連續的 EX: - 5的子樹dfs順序為4-7之間 - 2的子樹dfs順序為2-7之間 - 1的子樹dfs順序為1-8之間 因此我們把每個點的子樹區間記錄起來， 就可以用線段樹之類的資料結構維護 </div> ---- <div style="font-size:25px; text-align:left; margin-left:31%">  EX: - 修改5的子樹修改區間4-7 - 詢問2的子樹詢問區間2-7 </div> ---- 紀錄子樹區間 <div style="margin-left:-180px"> ```cpp= int ti=0; vector<pair<int,int>> dfsTime(n); int dfs(int x,int f){ dfsTime[x].first=dfsTime[x].second=ti++; for(auto i:edge[x]){ if(i==f) continue; dfsTime[x].second=max(dfsTime[x].second, dfs(i,x)); //紀錄最右界 } return dfsTime[x].second; } ``` </div> ---- <div style="font-size:25px"> 用資料結構(線段樹等)維護後，單次詢問/修改的複雜度 就從原本的$O(N)$降成O$(lgN)$ AC! </div> ---- ### 用樹壓平求LCA  | time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 | | ----- | - | - | - | - | - | - | - | - | - | - | - | - | - | | node | A | B | C | D | C | E | F | E | C | B | A | G | A | | depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 | ----  LCA(D,F) = C | time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 | | ----- | - | - | - | - | - | - | - | - | - | - | - | - | - | | node | A | B | C |[D | C | E | F]| E | C | B | A | G | A | | depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 | ---- 求出 u, v 的LCA為區間內的最小深度的點  | time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 | | ----- | - | - | - | - | - | - | - | - | - | - | - | - | - | | node | A | B | C | D | C | E | F | E | C | B | A | G | A | | depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 | ---- 記錄每個點的進來時間與離開時間 ```cpp= int ti = 0; //時間戳記 void dfs(int x,int f,int d){ dep[ti] = d; //記錄在當下時間點的節點深度 node[ti] = x; //記錄在當下時間點的節點 tin[x] = ti++; //紀錄點x進入時間點 for(auto i:edge[x]){ if(i != f) dfs(i,x,d+1); } dep[ti] = d; //記錄在當下時間點的節點深度 node[ti] = x; //記錄在當下時間點的節點 tout[x] = ti++; //紀錄點x離開時間點 } ``` ---- 因此可以用線段樹等資料結構求LCA ```cpp= int query(int u, int v){ if(tin[u] > tin[v]) swap(u, v); return segmentTree.query(tout[u], tin[v]); } ``` --- ## Eulerian Path & Circuit ### 歐拉路徑/迴路 - Eulerian Path 選一個點當起點，可以走過所有的邊剛好一次 - Eulerian Circuit 選一個點當起點，可以走過所有的邊剛好一次，**並且回到起點** ---- ## 存在歐拉路徑/迴路的充要條件 | | 歐拉迴路 | 歐拉路徑 | | ------ | -------- | -------- | | 無向圖 | 所有點的度數為偶數 | 度數為奇數的點數量不超過2 | | 有向圖 | 所有點入度等於出度 | <div style="font-size:20px;">全部點的入度出度一樣</br>或剛好一個點出度-1=入度</br> 另一點入度-1=出度，</br>其他點入度等於出度</div> | 並且**圖連通** ---- ## 求一組解 判斷是否有點出度數量-1=入度數量，有的話為起點 否則任意點都可以為起點 從起點開始 dfs 每次選一條未走過的邊繼續遞迴 在 dfs 後將點加入路徑中 遞迴完再將路徑反轉即為答案  ---- ## 程式碼 為了實作方便，每次選可以走的邊中最後一條，用完後可以 O(1) 刪除 當走到沒有邊可以走即結束 再把此點加進去路徑裡 ```cpp [|13|3,4,5,6|8|14,15] vector<int> path; void dfs(int x){ while(!edge[x].empty()){ int u = edge[x].back(); edge[x].pop_back(); dfs(u); } path.push_back(x); } int main(){ build_graph(); dfs(st); reverse(path.begin(),path.end()); for(int i:path) cout<<i<<' '; cout<<endl; } ``` ---- ## 串接英文單字 給你 $N(1 \le N \le 10^5)$ 個英文單字，問是否存在一種順序，使得相鄰的單字中，前面的單字字尾跟後一個單字字首相同 sample input 5 abc abb ba cde aea sample output abb ba aea abc cde ---- ## 轉換問題 可以把每個單字當成一條邊，一條從字首字母連到字尾字母的邊 而最多 26 個點 (26種字母) "abc" 即為一條從點 a 連到點 c 的邊 而題目要求每個單字用剛好一次，可以轉換為歐拉路徑 --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/488087) 提交期限到下星期三 4/13 23:59 截止