<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Graph Introduction to Competitive Programming 3/19 ---- ## Table of Contents - 複習: 圖上遍歷 DFS/BFS - DFS Tree - Topological Sort - DP on DAG - Cycle Detection - Euler Path/Circuit --- ## 複習: 圖上遍歷 DFS/BFS ---- <center> <img src="https://miro.medium.com/v2/resize:fit:1280/1*GT9oSo0agIeIj6nTg3jFEA.gif" style="margin: 0 auto; display: block; width: 400px"> </center> ---- ### BFS 實作範例 ```cpp! [|4-5|6-12|7|8-11|] bool vis[MXN]; void bfs(int s){ queue<int> q; q.push(s); vis[s]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i:edge[x]){ if(!vis[i]) q.push(i),vis[i]=1; } } } ``` ---- ### DFS 實作範例 ```cpp= void dfs(int x){ vis[x]=1; for(int i:edge[x]){ if(!vis[i]) dfs(i); } } ``` --- ## DFS Tree ---- 我們在 DFS 時多維護一個鄰接串列 $\text{child}[~]$ ```cpp= vector<int> child[MXN]; void dfs(int x){ vis[x] = 1; for(int i:edge[x]){ if(!vis[i]){ child[x].push_back(i); // 注意這裡 dfs(i); } } } ``` $\text{child}[~]$ 就會形成一棵 DFS tree，而 DFS tree 也是生成樹 ||自己證證看|| ---- 上述的 $\text{child}[~]$ 寫法我們其實不常用 然而 $\text{child}[~]$ 所形成的 DFS tree 算是 DFS 最核心的**性質**， 許多著名的圖論演算法都是利用這個機制在運作 像是 {拓樸排序|DFS version}、{找 SCC|Kosaraju's Algo.}、{找 BCC|Tarjan's Algo.}、{判二分圖|Bipartite Check}、Backtracking、各種樹上 DP、{算最大流|Dinic's Algo.} 全部都有用到 DFS 的性質在運作 ---- ### 節點的狀態 我們通常會幫節點上色來說明他目前是在 DFS 的什麼狀態: - 白點 : 尚未被發現的點 - 灰點 : 被發現，但後代還沒找完的點 (也就是鄰接串列尚未找完) - 黑點 : 被發現，且後代都找完的點 (也就是鄰接串列已經找完) 在 DFS 執行時，每個節點只會是這三種狀態 ---- 一個點還是白點，就去 dfs 該點 ```cpp! [8-11] void dfs(int x){ /* * x 剛剛被發現 (x 灰點) */ vis[x] = 1; for(int i:edge[x]){ // 代表 x -> i if(!vis[i]){ /* * 找到 i 是白點 => 送 dfs(i) */ dfs(i); } } /* * x 已處理完成 (x 黑點) */ } ``` ---- 送入 dfs 之後，該點就是灰點，接下來就會去看是否還有白點鄰居 ```cpp! [2-13] void dfs(int x){ /* * x 剛剛被發現 (x 灰點) */ vis[x] = 1; for(int i:edge[x]){ // 代表 x -> i if(!vis[i]){ /* * 找到 i 是白點 => 送 dfs(i) */ dfs(i); } } /* * x 已處理完成 (x 黑點) */ } ``` ---- 如果該點已經沒有鄰居了，就會跑到這個區塊，最後結束 ```cpp! [14-16] void dfs(int x){ /* * x 剛剛被發現 (x 灰點) */ vis[x] = 1; for(int i:edge[x]){ // 代表 x -> i if(!vis[i]){ /* * 找到 i 是白點 => 送 dfs(i) */ dfs(i); } } /* * x 已處理完成 (x 黑點) */ } ``` ---- 如果要看動畫來理解節點是如何改變狀態， 可以看[上個學期的講義](https://hackmd.io/@LeeShoWhaodian/2025-Tree-DSU#/4/2)，那邊有很多利用此性質的例子 ---- ### 邊的分類 DFS 執行完之後，會形成 DFS tree，邊也會被分成下列四種類型: - {樹邊|tree edge}: 在 DFS tree 的邊 - {後向邊|back edge}: 使樹上後代連回祖先的非樹邊 - {前向邊|forward edge}: 使樹上祖先連到後代的非樹邊 - {交叉邊|cross edge}: 連結兩棵不同子樹節點的非樹邊，兩點沒有血緣關係 ---- 舉例來說，左圖如果照數字順序 dfs，就會形成右圖 <center>  </center> --- ## {拓撲|Topological}{排序|Sort} 一種針對有向圖節點的排序方式 ---- 拓樸排序跟{拓樸學|Topology}一點關係都沒有 會這樣命名是因為早期數學家習慣把非幾何的空間關係稱做「拓樸」 現代數學中的拓樸已有嚴謹定義，跟圖論沒關聯 ||~~其實有一點 但不重要~~|| 但是「拓樸排序」一詞還是被保留下來 ---- ### Topological Ordering 若有種排序使得對任一條邊 $a\rightarrow b$ 在排序中 $a$ 都比 $b$ 還前面， 則稱為 Topological Ordering (中文也叫拓樸排序) <center>  </center> 圖中 $\langle 1,2,3,4,5,6\rangle$、$\langle 2,4,6,1,3,5\rangle$、$\langle 2,1,4,3,6,5\rangle\cdots$等 都是合法的拓樸排序 ---- ### 小試身手 這是海大圖書館中某本邏輯學的書，一個章節讀完之後才能讀箭頭所指的章節，否則先備知識會不足。聰明的你能夠排出一組拓樸排序嗎?🤭 <center>  </center> ---- 只有{有向無環圖|Directed Acyclic Graph} (DAG) 可以做拓樸排序， 若「圖中有環」or「圖為無向圖」，則此圖不會存在拓撲排序 <center>  </center> 換句話說，如果圖不是 DAG，則不存在拓撲排序 <!-- 如果對有環的有向圖做拓撲排序，會發現環上的點入度不會為 0，所以是沒辦法對有環的圖做拓撲排序的，但正好可以利用這個性質，用拓撲排序來找環。  --> ---- ### 想法 如何做拓樸排序呢? 觀察到 $\deg=0$ 的節點都可以當作是起點，訪問完之後就刪點拔邊 <center>  </center> ---- ### Kahn's Algorithm 重複以下步驟，直到沒有入度為 $0$ 的點 1. 找所有點 $v$ 滿足 $\deg(v) = 0$，將其放入 queue (此時 queue 都只有 $\deg = 0$ 的點) 3. 拿出 queue 中的點 $u$ 訪問，然後 pop 4. 拔掉所有 $u$ 連到鄰居的邊 (此步驟會產生新的入度為 $0$ 的節點) ---- 再舉個例子: 一開始入度為 0 的點都當作拓撲排序的起始點 把這些點放進 queue 裡面準備訪問 <center>  </center> ---- 放完之後，把 4, 8 連出去的邊移除 <center>  </center> 接著就繼續將入度為 $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]++; // v 的入度 +1 } ``` ---- ### 前處理 建完圖之後，開始拔入度為 $0$ 的點，可以用 queue 儲存要拔掉的點，依序拿出來 ```cpp= queue<int> que; for(int i = 0; i < n; i++){ if(deg[i] == 0) que.push(i); // 度數為 0 時推入 queue 中 } ``` ---- ### 遍歷 每次從 queue 裡面取出一個點，將他連到的點入度都減 1，減的時候順便確認那個點是否入度為 $0$ 了，這樣保證會按照拓樸排序遍歷所有節點 最後答案存在 $\text{ans}$ ```cpp= while (!que.empty()) { int u = que.front(); que.pop(); ans.push_back(u); // 結果存 ans for (int i : edge[u]) { deg[i]--; // 每次走訪完都先幫鄰居的入度 -1 if (!deg[i]) // 如果入度 == 0 則加入此節點 que.push(i); } } ``` ---- ### 複雜度 queue 裡面總共會跑過 $N$ 個點，每個點總共拔 $M$ 條邊 $O(N+M)$ ---- 可以知道queue裡面放的是「以當前的圖來說，入度為 0 的點們」，在這個queue裡面，要取哪一個點來當拓撲排序的下一個點都是沒差的。 當題目有跟你講說，「字典序最小」以及其他特殊限制的話，可以考慮用其他能 push 和 pop 的資料結構來模擬拓撲排序，例如`priority_queue`。 ---- 對於一個有環的有向圖去做拓撲排序，最後必定會形成一個或多個環 <center>  </center> 假設題目要你判斷圖中有沒有環，你可以拔完邊之後判斷是不是每個點都有跑進queue裡面過 ---- ### DFS 作法 觀察 DFS tree，如果從{根|root}節點往下走也會是合法的拓樸排序 <center>  </center> but 如何在 DFS 時知道誰是根節點? 誰是{葉|leaf}節點? ---- 一個節點如果是黑點，代表他的鄰居已經走完了 因此最先成為黑點的肯定是葉子，接下來才會一路往上變黑，直至根 <center>  </center> 最先訪問完鄰居的順序: $\langle 3,4,2,1\rangle$ 實際上做完的拓樸排序: $\langle 1,2,4,3\rangle$ ---- ### 實作 ```cpp= void dfs(int u) { vis[u] = true; for (int v : edge[u]) { if (!vis[v]) dfs(v); } ans.push_back(u); // 將順序存入 ans } void topo() { // 執行這個 for (int i = 1; i <= n; i++) { // 1-base if (!vis[i]) dfs(i); } reverse(ans.begin(), ans.end()); // 反轉答案 } ``` 記得最後要反轉 $\text{ans}$ 因為點的變黑順序跟拓樸排序的順序是相反的 ---- 時間複雜度: $O(N+M)$，跟 DFS 相同 ---- ### 例題： [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 \to 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) ---- $\text{dp}[i]$ 代表的是走到第 $i$ 個關卡有幾種方式 而他的 $\text{dp}$ 式也可以推成: $$ \text{dp}[i] = \sum\limits_{(i, j)\in E} \text{dp}[j] $$ 當然初始 $\text{dp}[1]=1$，因為起點當然只有 $1$ 種方式 ---- 由於題目給了你 DAG，所以你可以用拓撲排序的方式去做轉移 DFS / BFS 也可以遍歷整張圖阿! 為什麼不能直接用 DFS or BFS? <!-- .element: class="fragment" data-fragment-index="1" --> ---- 觀察一下轉移式: $\text{dp}[i] = \sum\limits_{(i, j)\in E} \text{dp}[j]$ <center>  </center> 假設要算 $\text{dp}[3]$ 的答案，那麼就要先算 $\text{dp}[1], \text{dp}[2]$，否則不 work $\Rightarrow$ 需要按照拓樸排序走訪才能轉移 ---- ### 舉個反例 設 $1$ 為起點，BFS 走訪順序: $\langle 1,2,4,3\rangle$ <center>  </center> 注意到 $4$ 已經計算完答案，才訪問到邊 $(3,4)$ 那 $\text{dp}[4]$ 就少算了 $\text{dp}[3]$ 的答案 $\Rightarrow$ WA ---- ### 再舉個反例 設 $1$ 為起點，DFS 走訪順序: $\langle 1,2,3,4\rangle$ <center>  </center> 注意到 $3$ 已經計算完答案，才訪問到邊 $(4,3)$ 那 $\text{dp}[3]$ 就少算了 $\text{dp}[4]$ 的答案 $\Rightarrow$ WA ---- ### 程式碼 ```cpp void topo() { 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); } } } ``` ---- 遇到在 DAG 上做 DP 要常要考慮計算的優先次序， 因此我們會做拓樸排序而不是 DFS 或 BFS ---- ### 例題: [Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g) 給 $N$ 個點、$M$ 條邊形成的 DAG，求最長路徑長度為何? $1\le N \le 10^5$ $1\le M \le 10^5$ ---- ### 想法 注意到轉移式: $$ \text{dp}[v] = \max_{(u,v)\in E}\{\text{dp}[u] + 1, \text{dp}[v]\} $$ 做拓樸排序 + DP 就結束了 ---- ### 例題: [UVA 00437](https://vjudge.net.cn/problem/UVA-437) 給妳 $n$ 種磚塊以及每種磚塊的長寬高，每種磚塊可以任意旋轉，你要把一些磚塊疊成一座塔，使得每個磚塊的底面長寬分別嚴格小於它下方磚塊的底面長寬，問你這座塔最大的高度可能是多少 $1 \le n \le 30$ ---- 跟上一題不一樣的是，題目沒有明確的給你整張圖，你需要自己生出一張圖才可以DP on DAG ---- ### 想法 可以觀察到 $n$ 最大為 $30$，對於一種磚塊，他會產生三種高度，一種高度會有兩種不同的長寬，因此可以生出 $n\times3\times2$ 種不同的磚塊 <center>  </center> ---- 由於下方磚塊的長寬要嚴格大於上方磚塊的長寬，可以把每個磚塊當作一個點，如果 磚塊$_{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)$ 把每個磚塊當作點： <center>  </center> ---- 如果 磚塊$_{b}$ 能疊在 磚塊$_{a}$上面，可以連 $a\rightarrow b$ 這條邊，邊權為 $b$ 的高 <center>  </center> DAG 就生出來了 ---- 接下來就要想一下怎麼 DP ---- ### 做法 定義 $\text{dp}[i]$ 為以 磚塊$_{i}$ 為頂端時，這個塔的最大高度為多少 對於每個 磚塊$_{i}$，$\text{dp}[i]$ 可以先初始化成這個磚塊的高度 ---- 假設要更新 $\text{dp}[i]$ 並且知道磚塊$_{j}$上面可以疊磚塊$_{i}$，可以去找每個 $\text{dp}[j]$ 的最大值對 $\text{dp}[i]$ 做更新 DP 轉移式長這樣: $$ \text{dp}[i]=\max(\text{dp}[i],\text{dp}[j]+\text{磚塊}_{i}\text{的高度}) $$ 其實就是在 DAG 上求從起點的最長路徑 ---- ### 離題 做任何 DP 時，必須保證子問題的解已計算，才能算原本問題的答案 其實 DP 抽象化之後都是在圖 (or 子圖) 用拓樸排序依序求解答案 --- ## 休息時間 --- ## 找環 (Cycle Detection) 在一個圖中找環、判環主要有三種方式: 1. 拓撲排序(有向圖) 3. DFS (有向圖) 4. DFS (無向圖) ---- ### 拓撲排序(有向圖) 想一下 Kahn's 拓樸排序的停止條件: **重複執行直到沒有 $\deg=0$ 的點** 但有沒有一種可能，程式停止之後仍有點沒被刪除? ---- 觀察到如果一張圖有環，做完拓樸排序之後會發現: **有向圖中，環上的節點入度至少為 $1$** <center>  </center> 找環的話就對剩下的圖去dfs，實做量稍為大一點但不難做 ---- ### DFS 測環 (無向圖) 我們會利用 dfs tree 的性質去判斷有沒有環 <center>  </center> ---- ### 再複習一次 dfs 時會將無向圖的邊分成: - {樹邊|tree edge}: dfs 時遇到新的點時走的邊 - {後向邊|back edge}: dfs 時遇到自己祖先的點時走的非樹邊 - {前向邊|forward edge}: dfs 時遇到自己後代的點時走的非樹邊 - {交叉邊|cross edge}: dfs 時連結兩棵不同子樹節點的非樹邊，兩點沒有血緣關係 ---- ### 想法 1. 如果要應付無向邊，就要**把連回復父節點的回邊判掉** $\because$ 無向圖中 $(u,v)$ 跟 $(v,u)$ 是同一條邊 2. 圖上有環 $\iff$ dfs 時存在非樹邊 (後向邊 or 前向邊 or 交叉邊) 3. 判斷非樹邊，只需要看對面那個點是否有拜訪過 $\Rightarrow$ 用 $\text{vis}[~]$ 維護即可 ---- ### 程式碼 (無向圖) ```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; // 如果在子孫已經出現環，回傳 true } return false; } ``` ---- ### DFS 測環 (有向圖) 如果只用 $\text{vis}[~]$ 判斷是否有拜訪過，在無向圖上可能不 work ---- 因為在有向圖中， cross edge 與 forward edge 也有可能走到拜訪過的點， 卻不會形成 cycle <center>  </center> ---- ### 再複習一次節點的狀態 我們通常會幫節點上色來說明他目前是在 DFS 的什麼狀態: - 白點 : 尚未被發現的點 - 灰點 : 被發現，但後代還沒找完的點 (也就是鄰接串列尚未找完) - 黑點 : 被發現，且後代都找完的點 (也就是鄰接串列已經找完) 在 DFS 執行時，每個節點只會是這三種狀態 ---- 觀察一下在 DFS 時節點的狀態與邊: - tree edge: 灰點 $\to$ 白點 - back edge: 灰點 $\to$ 灰點 (會產生環!!) - forward edge: 灰點 $\to$ 黑點 - cross edge: 灰點 $\to$ 黑點 ---- 可以定義 $\text{vis}[~]$ 陣列的狀態 - $\text{vis}[i]=0 \rightarrow$ 白點 - $\text{vis}[i]=1 \rightarrow$ 灰點 - $\text{vis}[i]=2 \rightarrow$ 黑點 如果 dfs 時，某個點 $a$ 遍歷到點 $b$，且 $\text{vis}[b]=1$ 的話，代表有環 ---- ### 程式碼 ```cpp= bool vis[N] = {0}; // 初始化為 0 (白點) 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 樹每個節點是從哪條邊走過來的，就可以找到圖上的一個環 ---- 定義 $\text{suc}[x]$ 為 $x$ 在 DFS tree 的父節點 若存在無向邊 $(u, v)$，且當前 DFS 是從 $v$ 走到 $u$， 代表 $v\to u$ 是 tree edge，因此就紀錄 $\text{suc}[u]=v$ 備註: 樹上每個點的父節點唯一 ---- ### 無向圖找環的程式碼： ```cpp= int vis[], suc[]; int dfs(int x, int v) { // v -> x 是 tree edge if (vis[x]) return x; suc[x] = v; // 紀錄 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; } ``` 有向圖留給大家自己練習>.< --- ## Euler Path/Circuit ---- ## [七橋問題](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) 在所有橋只能走過一遍的情況下，如何才能將所有橋走遍 換句話說，就是一筆畫問題 <center>  </center> ---- 現在的七橋： <center>  </center> 有關{歐拉|尤拉}的奇聞軼事可以去複習[上學期的講義](https://hackmd.io/@LeeShoWhaodian/2025-Graph-Theory#/2/3) ---- ### {歐拉|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 (\leq n \leq 15)$，要生出一個最小長度且字串中只有01兩種字元的字串 $s$，使得 $0\sim n-1$ 的二進制字串皆為 $s$ 的子字串 ```cpp input: 2 output: 00110 ``` 在 $00110$ 中，$00$、$01$、$10$、$11$ 都存在 ---- 這跟歐拉路徑有甚麼關係呢? 我們可以想一下如何轉換成圖 ---- 定義每個狀態都是一個點 在 $n=3$ 的情況下，會有長度為 $n-1$ 的四種狀態，分別為"00"、"01"、"10"、"11" <center>  </center> ---- 當前狀態加上0或1可以產生另外兩組狀態。 假設當前狀態是"01"，如果加上0，可以得到"010"，"010"可以代表的是"10"這個狀態。因此可以得到下圖 <center>  </center> ---- 得到答案的方式為:「從一個點開始DFS找歐拉迴路」 答案為起始點的狀態加上迴路上的所有邊權 <center>  </center> 如果從狀態"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)); // 結尾+0的下一個狀態 int a1 = ((i << 1) + 1) % (1 << (n)); // 結尾+1的下一個狀態 v[i].push_back(a0); v[i].push_back(a1); } ``` --- 題單連結:D