<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Graph Introduction to Competitive Programming 03/13 ---- * Topological Sort * DP on DAG * Cycle Detection * Euler Path/Circuit * Hamiltonian path/Travelling Salesman Problem --- ## 拓撲排序 ### Topological Sort 一種針對有向圖的排序方式  ---- ### 定義： 有 $n$ 個節點，編號從 $1$ 到 $n$，要制定一種排序使得 如果有一條邊 a $\rightarrow$ b, 在排序中 a 就會比 b 還前面。  ---- 若圖中「有環存在」or「為無向圖」，則此圖不會存在拓撲排序  換句話說，如果圖不是有向無環圖（DAG），不存在拓撲排序。 <!-- 如果對有環的有向圖做拓撲排序，會發現環上的點入度不會為 0，所以是沒辦法對有環的圖做拓撲排序的，但正好可以利用這個性質，用拓撲排序來找環。  --> ---- ### 做法(BFS)： 可以觀察到一開始入度為 0 的點都可以當作拓撲排序的起始點 會把這些點放進queue裡面  放完之後，把 4, 8 連出去的邊移除  接著就繼續將入度為 0 的點加入 queue 裡面， queue 是空的就做完了。 ---- ### 實作： 一開始建圖時，可以用一個陣列 deg[N] 紀錄每個點入度 ```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]==0)que.push(i); // 度數為 0 時推入queue中 } ``` ---- ### 實作： 每次從 queue 裡面取出一個點，將他連到的點入度都減 1，減的時候順便確認那個點是否入度為 0 了 ```cpp for(int i:edge[u]){ --deg[i]; if(deg[i] == 0){ // 當度數為 0 時，將節點推入佇列 que.push(i); } } ``` ---- ### 複雜度： queue裡面總共會跑過N個點，每個點總共拔M條邊 $O(N+M)$ ---- 可以知道queue裡面放的是「以當前的圖來說，入度為 0 的點們」，在這個queue裡面，要取哪一個點來當拓撲排序的下一個點都是沒差的。 當題目有跟你講說，「字典序最小」以及其他特殊限制的話，可以考慮用其他能 push 和 pop 的資料結構來模擬拓撲排序，例如`priority_queue`。 ---- 對於一個有環的有向圖去做拓撲排序，最後必定會形成一個或多個環  假設題目要你判斷圖中有沒有環，你可以拔完邊之後判斷是不是每個點都有跑進queue裡面過。 ---- ### 例題： [UVA: 10305 - Ordering Tasks](https://vjudge.net/problem/UVA-10305) 題意：給 n 個工作跟 m 組 pair 每組 pair 代表的是兩個工作的先後順序，前面的會比後面的早做 詢問任意一組合理的工作順序。 ---- 可以發現每組 pair 代表的是有向圖的一條邊，我們再圖上求出拓撲排序就可以找到合理的工作順序了。 ---- ### 例題： [CF 1385E - Directing Edges](https://codeforces.com/contest/1385/problem/E) 題意：給你包含「 n 個點、m${_1}$個無向邊、m${_2}$個有向邊」的圖 你要決定每個無向邊的方向使得這張圖為DAG。 無解輸出-1 ---- 可以發現對於每個有向邊，必定是不能改這條邊的方向，可以檢查有向邊構出的圖是不是有合理的拓撲排序。 對於某連接 u , v 的無向邊，判斷前面拓撲排序所構出的 編號$_{u}$ 和 編號$_{v}$ 來決定方向。 --- ## DP on DAG 就是在DAG上做DP ---- ### 例題：[Game Route](https://cses.fi/problemset/task/1681) 題意： 一個遊戲有 $n$ 個關卡，有 $m$ 個傳送器連結。 第 $i$ 個傳送器會從關卡 $u_i$ 傳送到關卡 $v_i$ 詢問從第 1 個關卡到第 n 個關卡有幾種方式？ 保證關卡不會經由傳送器回到自己(也就是沒有環) ---- 傳送器只能從關卡 u 到關卡 v，其實就是在說這張圖是一張有向圖，而題目有說沒有環，所以這就會是一張有向無環圖(DAG)。 ---- dp[i] 代表的是走到第 $i$ 個關卡有幾種方式 而他的 dp 式也可以推成 $dp[i] = \sum\limits_{edge(i, j)} dp[j]$ ---- 由於題目給了你DAG，所以你可以用拓撲的方式去做轉移。 ---- ### 程式碼： ```cpp void bfs() { queue<int>q;// 一樣放入度為0的點 for(int i=1;i<=n;i++){ if(deg[i]==0)q.push(i); } while(q.empty()==0){ int u=q.front(); q.pop(); for(int i:edge[u]){ dp[i]+=dp[u]; deg[i]--; if(deg[i]==0)q.push(i); } } } ``` ##### 其實還有DFS的作法，這堂課講完有時間再說。 ---- ### [UVA 00437](https://vjudge.net.cn/problem/UVA-437) 題意： 給妳n種磚塊以及每種磚塊的長寬高，每種磚塊可以任意旋轉，你要把一些磚塊疊成一座塔，使得每個磚塊的底面長寬分別嚴格小於它下方磚塊的底面長寬，問你這座塔的高度。 $1 \le n \le 30$ ---- 跟上一題不一樣的是，題目沒有明確的給你整張圖，你需要自己生出一張圖才可以DP on DAG。 ---- ## 想法 可以觀察到 n 最大為30，對於一種磚塊，他會產生三種高度，一種高度會有兩種不同的長寬，因此可以生出n\*3\*2種不同的磚塊。 ---- ## 想法 由於下方磚塊的長寬要嚴格大於上方磚塊的長寬，可以把每個磚塊當作一個點，如果 磚塊$_{b}$ 能疊在 磚塊$_{a}$上面，可以連 a $\rightarrow$ b 這條邊，邊權為b的高。 ---- ## 想法 假設有一種磚塊長寬高為(2,3,7) 那這種磚塊可以透過旋轉生出六種磚塊，他們的長寬高分別為： (2,3,7),(3,2,7),(2,7,3),(7,2,3),(3,7,2),(7,3,2) 把每個磚塊當作點：  ---- ## 想法 如果 磚塊$_{b}$ 能疊在 磚塊$_{a}$上面，可以連 a $\rightarrow$ b 這條邊，邊權為b的高。  DAG就生出來了 ---- 接下來就要想一下怎麼DP ---- ### 做法 定義dp[i]為以 磚塊$_{i}$ 為頂端時，這個塔的最大高度為多少。 對於每個 磚塊$_{i}$，dp[i]可以先初始化成這個磚塊的高度。 ---- ### 做法 假設要更新dp[i]並且知道磚塊$_{j}$上面可以疊磚塊$_{i}$，可以去找每個dp[j]的最大值對dp[i]做更新。 DP式長這樣： dp[i]=max(dp[i],dp[j]+磚塊$_{i}$的高度) --- ## 找環 ### Cycle Detection 在一個圖中找環主要有四種方式 1. 拓撲排序(有向圖) 2. dfs(有向圖) 3. dfs(無向圖) ---- ### 拓撲排序(有向圖) 有向圖的拓撲排序做法就跟前面一樣，可以觀察到如果一張圖有環，做完拓撲之後會發現：「有向圖中，環上的節點入度至少為一」 ---- 在有向圖的拓墣中，會把節點入度為 0 的點放進queue裡面，做完後去檢查有沒有點還沒有被放進queue裡，有的話就代表有環。 ---- ### dfs(無向圖) 在對一個圖做dfs，會產生一棵樹，叫做「dfs tree」 我們會利用這顆樹的性質去判斷有沒有環  ---- ### 無向圖 dfs 時會將無向圖的邊分成 tree edge 跟 back edge， * tree edge：dfs 時遇到新的點時走的邊 * back edge：dfs 時遇到自己祖先的點時走的邊 顯然可以發現，如果dfs時，back edge 存在，則圖中有環 ---- ### 程式碼： ```cpp int vis[N]; bool dfs(int x, int v) { if(vis[x]) return true; // 遇到祖先就代表有環，回傳 true vis[x] = 1; for(auto i:g[x]) { if(i == v) continue; if(dfs(i, x)) { return true; } } return false; } ``` ---- ### 有向圖 跟無向圖一樣，如果有回邊的話也會有環。 可以把節點分成三種，還沒走過的、下面節點還沒走完的、下面節點已經走完的。 ---- 可以定義vis[]陣列的狀態 - vis[i]=0 $\rightarrow$ 點i還沒被走過 - vis[i]=1 $\rightarrow$ 點i下面的節點還沒被走完 - vis[i]=2 $\rightarrow$ 點i下面的節點走完了 如果dfs時，某個點a遍歷到點b，並且vis[b]為1的話，代表有環 ---- ### 程式碼 ```cpp bool dfs(int x, int v) { if(vis[x] == 1) return true; // 當走到還沒走完的點，就代表有環 if(vis[x] == 2) return false; // 走到已經走完的節點，當沒事發生 vis[x] = 1; // 標記這個點還沒被走完 for(auto i:g[x]) { if(dfs(i, x)) { return true; } } vis[x] = 2; // 標記這個點已經被走完 return false; } ``` ---- ### 路徑 如果是要找環的路徑，可以將 dfs 改一下，由於環就是回邊造成的，因此環的路徑就是回邊的點到現在所在的點的這條路徑，只要記錄 dfs 樹每個節點是從哪條邊走過來的，就可以找到圖上的一個環。 ---- ### 無向圖找環的程式碼： ```cpp int vis[], suc[]; int dfs(int x, int v) { if(vis[x]) return x; suc[x] = v; vis[x] = 1; for(auto i:g[x]) { int tmp = dfs(i, x); // x 的祖先， if(tmp) { int now = x; while(now != tmp) { // 找從 x 到 tmp 的路徑 cout << now << ' '; now = suc[now]; } cout << tmp << ' ' << x << '\n';exit(0); } } return 0; } ``` 有向圖留給大家自己練習>.< --- ## 休息時間 --- ## [七橋問題](https://zh.wikipedia.org/zh-tw/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98) 在所有橋只能走過一遍的情況下，如何才能將所有橋走遍。  ---- 現在的七橋：  ---- ## 歐拉路徑/迴路 ### Euler Path/Circuit - 歐拉路徑: 選一個節點當起點，可以走過所有的邊剛好一次 - 歐拉迴路: 選一個節點當起點，可以走過所有的邊剛好一次，且最後回到原本的起點 ---- 首先我們要學會判斷出圖上存不存在歐拉路徑或歐拉迴路 同樣要區分有向圖和無向圖的情況 ---- ## 無向圖的歐拉迴路 由於每個頂點都會進入k次，出去也會是k次 因此滿足「每一個點的度數皆為偶數」並且「圖連通」 ---- ## 無向圖的歐拉路徑 歐拉路徑條件會比較寬鬆 如果有歐拉迴路就代表有歐拉路徑 由於可以選兩個點，一個點當起點，一個點當終點 那這個「起點和終點的度數可以是奇數」 其他點必須要是偶數 ---- ## 有向圖的歐拉迴路 這時候從無向圖改成有向圖了 因此要考慮入度和出度 如果圖中存在歐拉迴路 那代表「每個點的入度必須要等於出度」並且「圖連通」 ---- ## 有向圖的歐拉路徑 也是一樣可以選定起點和終點去走 起點的出度會等於入度+1 終點的入度會等於出度+1 其他點則是入度等於出度 ---- 歐拉證明了只要滿足以上條件，就一定可以構造出一個歐拉路徑/迴路，統整一下歐拉路徑/迴路成立的條件。 | | 歐拉迴路 | 歐拉路徑 | | ------ | -------- | -------- | | 無向圖 | 所有點的度數為偶數 | 度數為奇數的點數量不超過2 | | 有向圖 | 所有點入度等於出度 | <div style="font-size:20px;">全部點的入度出度一樣</br>或剛好一個點出度-1=入度</br> 另一點入度-1=出度，</br>其他點入度等於出度</div> | 並且**圖連通** ---- ### 找出一條歐拉迴路/路徑 從 `入度等於出度減一` 的點開始作為起點，並開始 dfs，每次選一條新的邊繼續遞迴，dfs 結束後將點加入路徑中，遞迴後將路徑反轉就是答案了。 ---- ### 程式碼 ```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; } ``` ---- 例題 : [De Bruijn Sequence](https://cses.fi/problemset/task/1692) 給你一個整數n，要生出一個最小長度且字串中只有01兩種字元的字串$s$，0~n-1的二進制字串皆為$s$的子字串。 $1 \leq n \leq 15$ input: ``` 2 ``` output: ``` 00110 ``` 在"00110"中，"00"、"01"、"10"、"11"都存在 ---- 這跟歐拉路徑有甚麼關係呢 我們可以想一下如何轉換成圖 ---- 定義每個狀態都是一個點 在$n=3$的情況下，會有長度為n-1的四種狀態，分別為"00"、"01"、"10"、"11"  ---- 當前狀態加上0或1可以產生另外兩組狀態。 假設當前狀態是"01"，如果加上0，可以得到"010"，"010"可以代表的是"10"這個狀態。 因此可以得到下圖  ---- 得到答案的方式為:「從一個點開始DFS找歐拉迴路」 答案為起始點的狀態加上迴路上的所有邊權  如果從狀態"00"開始走，以下是合理的歐拉迴路路徑 "00" $\rightarrow$ "01" $\rightarrow$ "10" $\rightarrow$ "01" $\rightarrow$ "11" $\rightarrow$ "11" $\rightarrow$ "10" $\rightarrow$ "00" $\rightarrow$ "00" 答案為"00"+"1"+"0"+"1"+"1"+"1"+"0"+"0"+"0" ---- 建圖: ```cpp= for(int i=0;i<(1<<(n-1));i++){ int a0=(i<<1)&(1<<(n-1));//結尾+0的下一個狀態 int a1=((i<<1)+1)&(1<<(n-1));//結尾+1的下一個狀態 v[i].push_back(a0); v[i].push_back(a1); } ``` --- ## 漢米爾頓路徑/環 ### Hamiltonian path ---- 給你一張圖，問你有沒有一種走法可以走過所有點，並且回到起始點  ---- 和歐拉路徑不一樣的是，點不可以重複走，可以不需要走過所有邊。 ---- 他會是一個NP-Complete問題，無法在多項式時間內做完。 最暴力的做法就是直接用`next_permutation`枚舉這個路徑的順序，再用O(n)的時間去判斷這個permutation可不可行。 複雜度為$O(n \cdot n!)$ ---- 假設題目真的出了漢米爾頓路徑的題目，通常n不會很大，因此可以狀態壓縮DP ---- 定義$dp[i][\{s\}]$為現在的點為$i$、走過的點記錄在點集$\{s\}$中 ```cpp dp[3][26]=dp[3][11010] 現在的點為3，走過1,3,4這三個點 ``` ---- 狀態轉移式： 假設存在 i $\rightarrow$ j 的邊，並且j不存在於點集{s}中 `dp[j][s|(1<<j)]`就可以從`dp[i][s]`去轉移 ```cpp! if( edge[i][j] && ( (1<<j) & s ) == 0 ){ dp[j][s|(1<<j)]=dp[i][s]; } ``` ---- 整體程式碼：程式碼: ```cpp= for(int s=0;s<(1<<n);s++){//枚舉點集合 for(int i=0;i<n;i++){//枚舉現在的點 if(s&(1<<i)==0)continue; for(int j=0;j<n;j++){//枚舉下一個點 if(i==j)continue; if( edge[i][j] && ( (1<<j) & s ) == 0 ){ dp[j][s|(1<<j)]=dp[i][s]; } } } } ``` 複雜度 : $O(n^2 \cdot 2^n)$ ---- ## 旅行推銷員問題(TSP) ### Travelling Salesman Problem 給定一個完全圖，每個邊都有邊權，求每一個點訪問剛好一次且最後要回到初始地的最短距離。 ---- 可以看出這個就是帶權的漢米爾頓迴路，所以也是以類似的方式去實作，放在習題讓大家自己去練習看看^^ --- ## Homework deadline: 3/24 link: [this](https://vjudge.net/contest/611493)