---
tags: 2023-i2cp
type: slide
slideOptions:
transition: fade;
# parallaxBackgroundImage: 'https://i.imgur.com/p1gBX3i.png'
# parallaxBackgroundImage: 'https://i.imgur.com/mH4xif0.png'
---
<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# Graph Algorithm 1
Introduction to Competitive Programming
03/01
<!-- aaa -->
----
* 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 還前面。
----
如果圖不是有向無環圖（DAG），不存在拓撲排序。
<!--
如果對有環的有向圖做拓撲排序，會發現環上的點入度不會為 0，所以是沒辦法對有環的圖做拓撲排序的，但正好可以利用這個性質，用拓撲排序來找環。
 -->
----
### 做法：
DFS/BFS 都可以做，這邊說 BFS 的
可以觀察到入度為 0 的點在拓撲排序中會在最前面，
放完之後，把 4, 8 連出去的邊移除
接著就繼續將入度為 0 的點加入 queue 裡面， queue 是空的就做完了。
----
### 實作：
一開始建圖時，可以用一個陣列 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); // 度數為 0 時推入佇列中
}
```
----
### 實作：
每次從 queue 裡面取出一個點，將他連到的點入度都減 1，減的時候順便確認那個點是否入度為 0 了
```cpp
for(int i:edge[u]){
--deg[i];
if(deg[i] == 0){ // 當度數為 0 時，將節點推入佇列
que.push(i);
}
}
```
----
### 複雜度：
拔邊的時候每條邊、點都會經過至少一次
$O(N+M)$
----
其實也不一定要用 queue 來實作，也可以用其他可以 push 跟 pop 的資料結構，只要是入度為 0 的點，都可以被拿來進行拓撲排序，順序不會影響正確性。
----
### 例題： [UVA: 10305 - Ordering Tasks](https://vjudge.net/problem/UVA-10305)
題意：給 n 個工作跟 m 組 pair
每組 pair 代表的是兩個工作的先後順序，前面的會比後面的早做
詢問任意一組合理的工作順序。
----
可以發現每組 pair 代表的是有向圖的一條邊，我們再圖上求出拓撲排序就可以找到合理的工作順序了。
----
### 例題： [CF 825E Minimal Labels](https://codeforces.com/problemset/problem/825/E)
題意：給一張有 n 個點 m 條邊的有向圖 (不一定連通)，給編號 1 ~ n 的點都貼上帶有數字的標籤，邊 u $\rightarrow$ v 的標籤 $label_u$ 要小於 $label_v$。
最後依照編號順序輸出標籤的數字，且字典序要最小。
----
直接拓撲加上優先佇列（由編號小的先拿）？
----
如果用正向拓撲加上優先佇列的話，下圖的答案會是
`6 5 2 1 4 3`?
但答案應該要是
`6 3 5 4 2 1`
----
### 為什麼會這樣呢？
如果有編號大的數字指向編號小的數字，可能讓編號小的數字較晚被分配到數字，導致字典序變大。
----
### 反過來想
如果對原圖建*反圖*，然後由大到小分配數字，這樣就只會造成編號大的數字比較晚分配到數字，字典序就會是最小的。
---
## DP on DAG
可以觀察到平常的 DP 我們會用到之前用過的答案，如果將這個過程轉換成圖的話，就會變成一張 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]$
----
### 程式碼：
```cpp
int dfs(int x) {
if(ans[x] != 0) return ans[x]; // 點已經被走過就回傳答案
int res = 0;
for(int i = 0; i < a[x].size(); i++) {
res = (res + dfs(a[x][i]) % 1000000007;
}
return ans[x] = res;
}
```
----
### [CSES Reachable Nodes](https://cses.fi/problemset/task/2138)
題意： 給一張 N 個點 M 條邊的 DAG，詢問從每個點作為起點，可以走到的節點數量
$1 \le n \le 5 * 10^4$
$1 \le m \le 10^5$
----
跟上一題不一樣的是，上一題要求的是到某個節點的方式有幾種，而這題要求的是可以走到幾個節點，因為沒有直接的結合律，好像沒容易簡單用 dp 去記錄答案。
----
### 做法
dp 改成記錄每一個點可以走到哪些點，
dp[1] = dp[2] $\cup$ dp[3] $\cup$ 1
----
### 做法
所以可以對每個節點都開一個大小為 n 的陣列，記錄這個節點可以走到哪些節點
轉移式
$dp[i] = dp[i] \cup dp[j]\ \forall \ (i \rightarrow j)$
不過這樣做的時間複雜度會是 $O(n ($陣列大小$) * m ($更新次數$))$ = $O(5 * 10^9)$ 還是會超過一秒。
----
### 優化
可以用 bitset 去優化轉移的時間，可以發現兩個 dp 取交集時，等價於用 bitset 做位元 or，我們就可以用 bitset 壓一下常數。
在 bitset 優化後，對陣列取交集變成 $O(\frac{n}{32})$
最後的複雜度變成 $O(\frac{5 * 10^9}{32}) \approx O(10^8)$，就會 AC 了！
----
### 程式碼：
```cpp
bitset<MXN> dp[MXN];
void dfs(int x) {
v[x] = 1;
dp[x][x] = 1;
for(int i : edge[x]) {
if(!v[i]) dfs(i);
dp[x] |= dp[i]; // 取兩個集合的交集
}
};
```
---
## 找環
### Cycle Detection
在一個圖中找環主要有兩種方式
1. 拓撲排序
2. dfs
----
### 拓撲排序
拓撲排序的做法就跟前面一樣，可以觀察到如果一張圖有環，做完拓撲之後：
* 有向圖：環上的節點的入度至少為一
* 無向圖：環上的節點的度數至少為二
----
可以根據以上性質用拓撲排序去找圖有沒有環
* 有向圖：節點度數為 0 時，將節點推入佇列內
* 無向圖：節點度數為 1 時，將節點推入佇列內
做完拓撲排序後如果有點沒有被推入佇列就代表圖內有環。
----
### dfs
dfs 時，會將圖變成一棵樹，我們利用的是這顆樹與其他邊的性質，可以分成有向圖跟無向圖兩種。
----
### 無向圖
dfs 時會將無向圖的邊分成 tree edge 跟 back edge，
* tree edge：dfs 時遇到新的點時走的邊
* back edge：dfs 時遇到自己祖先的點時走的邊
可以很直覺的發現，當一張無向圖有 back edge，就會有環，所以我們在 dfs 時，只要走到同一個點兩次，就可以確認這個圖有環
----
### 程式碼：
```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;
}
```
----
### 有向圖
跟無向圖一樣，如果有回邊的話也會有環。
不過 dfs 時會把邊分成四種，除了原本的兩種，還多了 cross edge 跟 forward edge，會留到之後再做介紹。
至於要怎麼判斷有向圖的回邊呢？
----
可以把節點分成三種，還沒走過的、下面節點還沒走完的、下面節點已經走完的，這樣子在 dfs 時遇到下面節點還沒走完的時，就代表走的那條邊是回邊了。
----
### 程式碼
```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)
在所有橋只能走過一遍的情況下，如何才能將所有橋走遍。
Note:
星報氣流展
----
現在的七橋：
----
## 歐拉路徑/迴路
### Euler Path/Circuit
- 歐拉路徑: 選一個節點當起點，可以走過所有的邊剛好一次
- 歐拉迴路: 選一個節點當起點，可以走過所有的邊剛好一次，且最後回到原本的起點
----
要怎麼找出一條歐拉路徑/迴路呢？
可以先從判斷一張圖有沒有歐拉路徑開始
一樣分成有向圖和無向圖的判斷方式
----
### 無向圖
可以從節點的角度來觀察，每個點都有不同的度數，而度數代表的是可以進出這個點幾次，如果一個點的度數是奇數，如果要走完這樣的節點的邊，需要進出 $\lfloor \frac{n}{2} \rfloor$ 次，且最後會停在這個節點，反之，如果度數是偶數，則是要進出 $\frac{n}{2}$ 次，且除了起始點以外，會離開這個節點。
----
### 無向圖的歐拉迴路
一張無向圖要有歐拉迴路，對點的要求是每個節點進出都不會被卡在裡面，如果有度數為奇數的點，走完邊的結果會是卡在裡面，因此無向圖歐拉迴路需要無向圖節點的度數都是偶數。
----
### 無向圖的歐拉路徑
一張無向圖要有歐拉路徑的條件比迴路寬鬆一點，由於你可以從一個點開始，另一個點結束，所以你可以同時有兩個度數為奇數的點，一個點當起點，另一個點當終點
----
### 有向圖的歐拉迴路
有向圖跟無向圖不同的是要完整走完一個節點的邊，需要的是入度與出度相同，只要滿足這條件，就有可能會有歐拉路徑。
----
### 有向圖的歐拉路徑
與無向圖相同，可以從一個點開始，另一個點結束，因此有向圖有歐拉路徑的條件是一個點的出度等於入度減一，另一個點的入度等於出度減一，這樣就可以從入度等於出度減一的點作為起點，出度等於入度減一的點作為終點。
----
歐拉證明了只要滿足以上條件，就一定可以構造出一個歐拉路徑/迴路，統整一下歐拉路徑/迴路成立的條件。
| | 歐拉迴路 | 歐拉路徑 |
| ------ | -------- | -------- |
| 無向圖 | 所有點的度數為偶數 | 度數為奇數的點數量不超過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 序列
de Bruijn 序列是一個字串，這個字串包含了長度為 n 且每個字母有 k 種可能的字串
例如，當 n = 3, k = 2 時，de Bruijn 序列的其中一種可能性是 0001011100，他有 000, 001, 010, 011, 100, 101, 110和111 的子字串
通過一些證明，de Bruijn 序列的長度固定會是 $k^n + n - 1$
----
首先，我們對所有長度為 n - 1 的子字串作為節點建立一張圖
一樣以 n = 3, k = 2 為例：
每個節點連出連出的邊會有 k 種，而連到的節點則是將本來所在節點的第一個 bit 刪掉，並在後面將邊上代表的 bit 放在最後面。
----
得到 de Bruijn 序列的方式就是，從任意一個點開始，找到圖的歐拉迴路， de Bruijn 序列就會是起始節點的字串加上邊上所有的bit。
----
為什麼這樣會是好的呢，可以觀察到，序列 abc 可以通過 ab 節點的前面兩個節點連接的邊構成，而 c 就會是連出去的邊，我們只要找到任意的歐拉路徑，代表就可以構出所有長度為 n 且有 k 種可能性的子字串
<!-- 走到任意一個節點前 n - 1 步，剛好會構出所在節點長度為 n - 1 的字串，而要用長度為n - 1 的子字串構出長度為 n 的字串需要的條件就是加上一個 bit，所以這個節點連出去的 k 條邊就是連出去的可能性 -->
----
### 建圖程式碼：
n = n, k = 2 的圖的建圖方式
```cpp
for (int i = 0; i < (1<<(n-1)); i++){
v[i].push_back(((i<<1))&((1<<(n-1))-1));
v[i].push_back(((i<<1)+1)&((1<<(n-1))-1));
}
```
把圖建完跑一遍歐拉路徑就是一組合法解了
---
## 漢米爾頓路徑/環
### Hamiltonian path
給定一張圖，是否有一條路徑恰好走過所有節點剛好一次。
與歐拉路徑類似，只是要遍歷的變成了點
----
與歐拉路徑的問題不同，經過證明，漢米爾頓路徑是 NP-C 的問題，沒有多項式時間的解決方式，
最直接的做法就是對點集找全排列 (`next_permutation`)，對每種排列花 $O(n)$ 時間看可不可行，時間複雜度 $O(n * n!)$
<!-- NPC dp -->
----
由於每個點只能走過一次，所以可以將點集分成 `已經走過的`、`還沒走過的`
定義 `dp[i][{s}]` 為當前在點 i，且已經拜訪過 {s} 這些點了
----
實作時由於 n 不會很大， {s} 會用狀態壓縮的方式去實現，用整數的 bit 去記錄 s 的集合內含有哪些數字。
```
i = 3，{s} = 11001 代表的就是已經走過 0、3、4 三點，且目前在 3 的位置
```
----
狀態轉移式：當有一條 i 到 j 的邊且 j 不屬於 s 時 $dp[j][{s} \cup j] = dp[i][{s}]$
```cpp
if(((1 << i) & s) && !((1 << j) & s)) {
dp[j][s | (1 << j)] = dp[i][s];
}
```
----
### 程式碼：
```cpp
for(int i = 1; i < (1 << n); i++) {
for(int j = 0; j < n; ++j) {
if(!((1 << j) & i)) {
for(int k = 0; k < n; k++) {
if(j == k) continue;
if((1 << k) & i) {
dp[j][i | (1 << j)] = dp[k][i];
}
}
}
}
}
```
複雜度: $O(n^22^n)$
----
## 旅行推銷員問題(TSP)
### Travelling Salesman Problem
給定一個完全圖，每個邊都有邊權，求每一個點訪問剛好一次且最後要回到初始地的最短距離。
----
可以看出這個就是帶權的漢米爾頓迴路，所以也是以類似的方式去實作，放在習題讓大家自己去練習看看^^
---
## Homework
deadline: 3/8
link: [this](https://vjudge.net/contest/544447)
Google Drive
Gist
Clipboard
Sign in with Wallet
