2020 Week 5: Graph Structures

--- tags: 成大高階競技程式設計 2020, ys --- :+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1: 2020 Week 5: Graph Structures = 本週要繼續介紹些基本的資料結構並且接下來將使用這些資料結構構造(解釋)一些演算法 > 底下的術語挺多的，各位不需馬上就得記起來，等到未來碰到再回來多複習幾遍 # Graph 圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構 ![](https://i.imgur.com/Z5A39X3.png) 圖的術語： * 點 (vertex)：組成圖的最基本的元素 * 邊 (edge)：點與點的關係 * $u$ 的鄰點 (neighbors)： $u$ 透過一個邊連到的所有點 * 有向圖 (directed graph)：邊帶有**方向**性 * 無向圖 (undirected graph)：每條邊都是**雙向**的 * 道路 (walk[^7])：點邊相間的序列， e.g. $v_0e_1v_1e_2v_2..e_nv_n$ * 行跡 (trail)： **邊不重複**的道路 * 路徑 (path)： **點不重複**的道路[^8] * 環 (cycle)：路徑的**起**點與**終**點連接後形成環 * 度 (degree)：與該點連接的邊數量 (無向性) * 入度 (in-degree)：連到該點的邊數量 (方向性) * 出度 (out-degree)：該點往外連的邊數量 (方向性) * 走訪/遍歷 (traversal/search)：走完全部的點或邊 > 口語上常會把路徑表示成道路，但根據多數的圖論書籍，這兩者定義是不同的在討論圖的邊，常會有 $u$ 是邊起點與 $v$ 是邊終點的慣例用符 ```graphviz digraph { rankdir="LR"; u -> v; } ``` > 上面這就是一種有向圖 ## 圖的儲存通常圖用鄰接表 (adjacency list) 或鄰接矩陣 (adjacency matrix) 儲存資料 ### 鄰接表 ```cpp struct edge { int u, v, w; }; // 兩個相鄰點與邊權重 vector<edge> E; int main() { : . while (M--) { scanf("%d%d%d", &u, &v, &w); E.push_back({u, v, w}); } } ``` 直接紀錄所有邊(兩點與權重) 或是 ```cpp struct vertex { int v, w; }; // 鄰點與邊權重 vector<vertex> E[MAXN]; int main() { : . while (M--) { scanf("%d%d%d", &u, &v, &w); E[u].push_back({v, w}); } } ``` 為每個點紀錄其所有鄰點與之間的權重 ### 鄰接矩陣 ```cpp int E[MAXN][MAXN]; int main() { : . while (M--) { scanf("%d%d%d", &u, &v, &w); E[u][v] = w; } } ``` 為每對點紀錄邊的關係 (有無權重可代表是否有邊) > 使用鄰接矩陣要注意空間成本 --- # Tree 樹 (Tree)，這個資料結構在圖像化看起來像顆倒掛的[樹](https://zh.wikipedia.org/wiki/%E6%A0%91)，根在上，而葉子在下。 ![](https://i.imgur.com/j8BGaid.png) 樹的術語及特點： * 樹是種**有向無環連通圖** * 節點 (node)：樹上的點不使用圖的術語：點 (vertex) * 父 (parent)：節點能**反向**拜訪的**第一個**節點 * 子 (child)：節點能**正向**拜訪的**第一個**節點 * 祖先 (ancestor)：節點能反向拜訪的所有節點 * 孫子 (descendant)：節點能正向拜訪的所有節點 * 根 (root)：沒有父節點的節點 * 葉 (leaf)：沒有子節點的節點 * 深度 (depth)：節點的深度為從根到該節點所經過的邊數 * 森林 (forest)：一個集合包含所有不相交的樹 * ==**每個非根節點只有一個父節點**== > 在數學上的圖論領域，通常樹是種**無向**無環的連通圖 ## 樹的儲存將節點本身的資料，以及連接的其他節點位置以 `node` 結構保存下來 ```cpp struct node { int val; // value node *ch1, *ch2, *ch3, *ch4; // vector<node*> ch; } ``` > 這是每個節點至多有四個孩子的樹 --- # Union-Find Forest (併查森林) 考慮設計一個結構，它要能存放一些集合，且這些集合之間**沒有相同元素** 這樣的集合族稱作 **Disjoint sets** > Disjoint sets 通常應用在"**分類**"問題中直觀的想法是將每個**集合有哪些元素**，用陣列或連結串列紀錄起來而常見的集合操作有，新增、刪除、(取)聯集、取交集(?)、取集合大小 >可以思考一下這些操作的複雜度要多少但併查森林則是將紀錄方式從 "集合有哪些元素" 改為 "**元素屬於哪個集合**" ## Initialization ```cpp for (int v = 1; v <= N; v++) group[v] = v; ``` ```graphviz graph { 1; 2; 3; 4; "..."; "N-1"; N; } ``` ## Find Find 會尋找某個元素屬於哪個集合 ```cpp int Find(int v) { if (v == group[v]) return v; return Find(group[v]); } ``` 假設有元素 $1$ ~ $5$，其中 $1,2$ 一組，$3,4,5$ 一組。 ```graphviz digraph { 1 -> 2; 3 -> 4; 4 -> 5; } ``` 下 `Find(5)` 指令，會回傳 $3$ ### Path Compression 稍微想像一下可發現，若樹長這樣： ```graphviz digraph { rankdir="LR"; p[label = "..."]; 3 -> 4 -> 5 -> "..." -> i -> p -> N; } ``` 那麼明顯 `Find(i)` 的複雜度為 $O(N)$ 直覺的，如果樹不是長得這麼長，而是**一個個節點**都直接接在 $3$ 底下那麼 `Find(i)` 的複雜度似乎就能下降了。所以每當回溯時就順便把最上層 group 的標號[^10](也就是 $3$) 給所有拜訪完的節點 $i$ 也就是改寫為： ```cpp int Find(int v) { if (v == group[v]) return v; return group[v] = Find(group[v]); // Path Compression } ``` 於是原本的森林下 `Find(5)` 指令 ```graphviz digraph { 1 -> 2; 3 -> 4; 4 -> 5; } ``` 森林會變成： ```graphviz digraph { 1 -> 2; 3 -> 4; 3 -> 5; } ``` ## Union Union 會將兩個集合合併起來 > 再次提醒：此集合族是 disjoint 的 ```cpp void Union(int u, int v) { group[Find(u)] = Find(v); } ``` 若對下圖這樣的情況，做 `Union(4, 2);` 也就是將 $4$ 的 root $3$ 合併到 $2$ 的 root $1$ ```graphviz digraph { 1 -> 2; 3 -> 4; 3 -> 5; } ``` 則上圖會變為下圖這樣： ```graphviz digraph { 1 -> 2; 1 -> 3 -> 4; 3 -> 5; } ``` 有種方式稱作 [Union by rank/size](https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union)，將 rank/size 小的樹併到 rank/size 大的樹下，可加快許多。 #### 範例 [UVa OJ 879 Circuit Net](https://uva.onlinejudge.org/external/8/879.pdf)： ```cpp int u, v; cin.ignore(); // for getline while (getline(cin, pins)) { if (pins.empty()) break; // for getline stringstream sin(pins); while (sin >> a >> b) Union(a, b); } int cnt = 0; for (int i = 1; i <= N; i++) if (group[i] == i) cnt++; ``` >`std::stringstream` 是很方便的東西，不過據說效率不夠優。 #### 練習： [UVa OJ 10583 Ubiquitous Religions](https://uva.onlinejudge.org/external/105/10583.pdf) [UVa OJ 11987 Almost Union-Find](https://uva.onlinejudge.org/external/119/11987.pdf) [TIOJ 1192 鑰匙設計](https://tioj.ck.tp.edu.tw/problems/1192) [CODEFORCES 1253D Harmonious Graph](https://codeforces.com/contest/1253/problem/D) # 搜尋有了圖，有了樹，可以開始討論這回事了 - 狀態：搜尋所能觸及到的可能性/目標 - 狀態轉移：每當狀態改變後，前個狀態到下個狀態的過程 - 狀態空間：若把狀態看作**點**，而狀態轉移看作**邊**，狀態空間為包含這些點與邊的**圖** 回憶一下上面曾介紹的術語： - 走訪/遍歷 (traversal/search)：走完全部的點或邊遍歷也是種搜尋，但"走完"可能得付出龐大的時間成本，或是空間成本根據狀態空間規模，須用一些手段使得能更快速的找到所想要的東西。本章使用的圖論符號慣例： - $V$ (Vertex) 表節點集合，表達單一點常用 $u$, $v$ - $E$ (Edge) 表邊集合，通常起點用 $u$、終點用 $v$ 作為點符號 > $u \to v$ 邊可寫成 $(u, v) \in E$ 或是 $uv \in E$ # 深度優先搜尋 (Depth-first Search) 顧名思義，要盡量以深層的方式搜尋，以下簡稱 DFS ```graphviz graph { node[label=""]; a -- e; a -- b; b -- c; c -- d -- b; c -- e; c -- f; b -- g; b -- h -- a; h -- i -- b; h -- j; a -- k; k -- l; a -- m; m -- n; m -- o -- a; } ``` 走訪方式：每拜訪一點就往其一鄰點拜訪下去。 >這裡的走訪為走遍所有**點** (而非邊) >若中途碰到曾走過的點不往下繼續走。[^dfs-1] ```graphviz graph { edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 2; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 1 -- 6; 6 -- 3; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 3 -- 5 -- 6; 3 -- 2; 3 -- 4; 6 -- 7; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 6 -- 9; 9 -- 1; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 9 -- 8 -- 6; 9 -- 10; 1 -- 11; 11 -- 12; 1 -- 13; 13 -- 14; 13 -- 15; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 15 -- 1; } ``` 按照上圖，走訪**順序**為 $1$ 依照自然數列開始走訪到 $15$。 DFS 走過的道路為**樹**，稱此樹為 DFS 樹： ```graphviz digraph { edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1[ xlabel = <0> ]; 2[ xlabel = <1> ]; 11[ xlabel = <1> ]; 13[ xlabel = <1> ]; 3[ xlabel = <2> ]; 12[ xlabel = <2> ]; 14[ xlabel = <2> ]; 15[ xlabel = <2> ]; 4[ xlabel = <3> ]; 5[ xlabel = <3> ]; 6[ xlabel = <4> ]; 7[ xlabel = <5> ]; 8[ xlabel = <5> ]; 9[ xlabel = <6> ]; 10[ xlabel = <7> ]; 1 -> 2; 2 -> 3; 3 -> 4; 3 -> 5; 5 -> 6; 6 -> 7; 6 -> 8; 8 -> 9; 9 -> 10; 1 -> 11; 11 -> 12; 1 -> 13; 13 -> 14; 13 -> 15; } ``` (圖上節點左上角的數字代表深度) ```cpp void dfs(int u, int dep) { // dep := depth for (int v: E[u]) { if (vis[v]) continue; vis[v] = true; dfs(v, dep+1); } } ``` > 這裡 for 迴圈採用 [Range-based](https://en.cppreference.com/w/cpp/language/range-for) 寫法其中 `vis[i]`[^convention] 為 `true` 代表此點已**拜訪完**，下次遇到此點直接略過。所以在開始進行走訪前，將起點設為**拜訪完**： ```cpp vis[root] = true; // root 代表走訪此圖的起點 dfs(root, 0); ``` DFS 除了能夠以上述遞迴方式呈現，也可以採用 **stack** 來實作： ```cpp stack<tuple<int, int, int>> dfs; dfs.emplace(root, 0, 0); vis[root] = true; while (!dfs.empty()) { auto [u, cur, dep] = dfs.top(); dfs.pop(); // cur := current index for (int i = cur; i < E[u].size(); i++) { int v = E[u][i]; if (vis[v]) continue; vis[v] = true; dfs.emplace(u, i, dep); // 往下個深度前先保存當前狀態 dfs.emplace(v, 0, dep+1); break; } } ``` >雖然實務上是以遞迴方式實作為主流，但還是建議讀懂這份程式碼 #### 練習： [LeetCode 102 Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal) [LeetCode 236 Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree) ## 狀態空間搜尋[^dfs-2] 搜尋某個**狀態**，可以利用**函式**與**參數**表示例如會把 `f(1, 2, 3)` 和 `f(3, 4, 5)` 這樣的函式呼叫，當作不同的狀態去接觸(求解)它。 #### 範例 [UVa OJ 572 Oil Deposits](https://uva.onlinejudge.org/external/5/572.pdf)：題目要求一個區域中有幾個**連通**圖所謂的連通，就是圖中任意兩點間至少有一條路徑當接觸到 `dfs(r, c)` 狀態時，代表這裡有包含座標 $(r, c)$ 的 oil deposit (前提 `plot[r][c]` 為 `'@'`) 而 DFS 走訪時，只需確保不再重複走到走過的點，所以走過就設 `'*'` ```cpp void dfs(int r, int c) { if (plot[r][c] == '*') return; plot[r][c] = '*'; for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) //雙重迴圈讓八個方位都走 if (r+dr >= 0 && r+dr < m && c+dc >= 0 && c+dc < n) dfs(r+dr, c+dc); } ``` *只要是連通圖，DFS 都能把此圖走訪完* 這裡簡單算走進幾次連通圖就好 ```cpp int count = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (plot[i][j] == '@') { dfs(i, j); count++; } ``` #### 練習： [LeetCode 113 Path Sum II](https://leetcode.com/problems/path-sum-ii) \* [LeetCode 437 Path Sum III](https://leetcode.com/problems/path-sum-iii) # 廣度優先搜尋 (Breadth-first Search) 顧名思義，要盡量以寬廣的方式搜尋，以下簡稱 BFS ```graphviz graph { node[label=""]; a -- e; a -- b; b -- c; c -- d -- b; c -- e; c -- f; b -- g; b -- h -- a; h -- i -- b; h -- j; a -- k; k -- l; a -- m; m -- n; m -- o -- a; } ``` 走訪方式：每拜訪一節點就將其全部鄰點拜訪過。 >同 DFS，碰到曾走過的點則不往下繼續走 ```graphviz graph { edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 2; 1 -- 3; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 3 -- 8; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 8 -- 10; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 10 -- 3; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 8 -- 2; 8 -- 15; 3 -- 9; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 3 -- 4; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 4 -- 1; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 4 -- 11; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 11 -- 3; 4 -- 12; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 5; 5 -- 13; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 6; 6 -- 14; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 6 -- 7; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 7 -- 1; } ``` 按照上圖，走訪**順序**為 $1$ 依照自然數列開始走訪到 $15$。對於一個**點**，會經歷以下階段： 1. 未拜訪：不曾進入隊列 2. 拜訪中：進入隊列 3. 拜訪完：離開隊列則 BFS 的流程為： 1. 將起點(root)加入隊列中 2. 每次將一個拜訪中的點 $u$ 的所有**未拜訪鄰點**加進隊列，而 $u$ 就此拜訪完畢 3. 重複動作 2. 直至隊列為空 > 若圖是連通圖，則 BFS 會將所有點都拜訪過 ```cpp queue<int> Q; Q.push(root); //root 代表走訪此圖的起點 vis[root] = true; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto& v: E[u]) { if (vis[v]) continue; vis[v] = true; Q.push(v); } } ``` > 根據條件應將不合法的走法濾掉，在 `Q.push()` 之前可判斷一下。 >BFS 跟 DFS 結構只差在 stack 和 queue，除此之外兩者是非常相似的與 DFS 同樣，由於不會走訪曾走過的點，所以 BFS 走完後也會有個 BFS 樹： ```graphviz digraph { 1[ xlabel = <0> ]; 2[ xlabel = <1> ]; 3[ xlabel = <1> ]; 4[ xlabel = <1> ]; 5[ xlabel = <1> ]; 6[ xlabel = <1> ]; 7[ xlabel = <1> ]; 8[ xlabel = <2> ]; 9[ xlabel = <2> ]; 10[ xlabel = <2> ]; 11[ xlabel = <2> ]; 12[ xlabel = <2> ]; 13[ xlabel = <2> ]; 14[ xlabel = <2> ]; 15[ xlabel = <3> ]; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -> 2; 2 -> 8; 8 -> 15; 1 -> 3; 3 -> 9; 3 -> 10; 3 -> 11; 1 -> 4; 4 -> 12; 1 -> 5; 5 -> 13; 1 -> 6; 6 -> 14; 1 -> 7; } ``` ## 最短步數搜索地圖**起點到任意點**的最短步數/路徑，例如地圖上 `*` 代表牆(不能走)，`$` 代表路，`%` 是起點，`@`是終點且每一步只走上下左右一格： ``` * * * * * * * * * * * * * * $ % $ $ * * * $ $ $ $ * * $ * * * $ * $ * * * $ * * * $ * $ $ $ * $ * * * $ * $ * $ $ $ * * * $ $ * * $ * $ $ * * * $ $ $ * * * $ * * @ * * $ * $ $ $ * * $ * * $ * $ * $ * * $ $ $ $ $ $ * * * * * * * * * * * * * ``` BFS 可以應用在這[^bfs-1]： ```haskell * * * * * * * * * * * * * * 1 0 1 2 * * * 5 4 3 2 * * 3 * * * 6 * 4 * * * 4 * * * 7 * 5 6 7 * 5 * * * 8 * 6 * 8 7 6 * * * 9 10 * * 9 * 7 8 * * * 11 12 13 * * * 9 * * 21 * * 14 * 12 11 10 * * 20 * * 15 * 13 * 11 * * 19 18 17 16 15 14 * * * * * * * * * * * * * ``` 其中上面數字代表**深度**。這個走法就跟[粘菌走迷宮](https://www.youtube.com/watch?v=czk4xgdhdY4)同樣 #### 範例 [UVa OJ 11624 Fire!](https://uva.onlinejudge.org/external/116/11624.pdf)：最開始先將 Joe 與各火點放進 queue 中，以便讓 BFS 以此為起點走訪： ```cpp for (int r = 0; r < R; r++) { scanf("%s", input); for (int c = 0; c < C; c++) { if (input[c] == '#') maze[r][c] = 0; if (input[c] == '.') maze[r][c] = INF; if (input[c] == 'J') J.push({r, c, 0}), maze[r][c] = INF, vis[r][c] = true; if (input[c] == 'F') F.push({r, c, 0}), maze[r][c] = 0; } } ``` (其中 `INF`[^convention] 為一個非常大的數字，例如 `int` 的上限) Joe 不能被火燒到，所以 Joe 一定要**走得比火快** 由此，算出各點何時火會燒過來就能判斷 Joe 是否能比火先到搜尋火到各點的**最短路**： ```cpp while (!F.empty()) { point f = F.front(); F.pop(); for (int d = 0; d < 4; d++) { int nr = f.r+dr[d], nc = f.c+dc[d]; if (nr == R || nc == C || nr < 0 || nc < 0 || maze[nr][nc] != INF || maze[nr][nc] == 0) continue; maze[nr][nc] = f.t + 1; F.push({nr, nc, f.t+1}); } } ``` 其中 `point` 結構三個變數為 **r**ow, **c**olumn 與 **t**ime (火抵達的時間) 並利用 dr 與 dc 以當前所在點走遍四個方向： ```cpp /* 左, 右, 下, 上 */ int const dr[] = {0, 0, -1, 1}; int const dc[] = {-1, 1, 0, 0}; ``` 現在 maze (也就是地圖) 上有紀錄火到的時間了。接下來讓 Joe 去尋找最短路： ```cpp int escape = -1; while (!J.empty()) { point j = J.front(); J.pop(); if ((j.r == R-1 || j.c == C-1) || (j.r == 0 || j.c == 0)) { escape = j.t + 1; break; } for (int d = 0; d < 4; d++) { int nr = j.r+dr[d], nc = j.c+dc[d]; if (vis[nr][nc] || j.t + 1 >= maze[nr][nc]) continue; vis[nr][nc] = true; J.push({nr, nc, j.t+1}); } } ``` `j.t + 1 >= maze[nr][nc]` 就能看 Joe 走這點是不是會被火燒最後判斷走到邊界，就成功逃脫了！ #### 練習： [UVa OJ 532 Dungeon Master](https://uva.onlinejudge.org/external/5/532.pdf) [LeetCode 542 01 Matrix](https://leetcode.com/problems/01-matrix) [LeetCode 994 Rotting Oranges](https://leetcode.com/problems/rotting-oranges) [STEP5 0127 攻略妹妹](http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0127) [LeetCode 127 Word Ladder](https://leetcode.com/problems/word-ladder) [UVa OJ 11234 Expressions](https://uva.onlinejudge.org/external/112/11234.pdf) [UVa OJ 1599 Ideal Path](https://uva.onlinejudge.org/external/15/1599.pdf) \* [CODEFORCES 1307D Cow and Fields](https://codeforces.com/problemset/problem/1307/D) # Backtracking >利用各種可得的限制來做搜尋目標中的偷吃步八皇后問題[^bt-1]：西洋棋盤上任意擺放八個皇后彼此都不互攻的情況有幾種？如下圖是其中一種合法的擺法 ![](https://i.imgur.com/c6rMMbY.png) [^bt-1] 若想著把每一種任意擺放可能性列出來，再來挑選可行的盤面，將有 $\binom{64}{8} = 4426165368$[^combination] 種盤面要產，明顯的程式會跑很久而兩個皇后放在同個 row 或 column 上一定會互攻，所以只需在每個 row 或 column 擺放一個皇后就好： ```cpp int dfs(int row) { if (row == 8) return 1; int sum = 0; for (int col = 0; col < 8; col++) if (check(row, col)) { board[row] = col; // 在 (row, col) 放置一個皇后 sum += dfs(row + 1); } return sum; } ``` 這邊的 `check(r, c)` 就是本節的主題了，在轉移狀態(盤面)前，若能預感(?)這狀態不是想要的，就中斷轉移，然後 backtrack 到原狀態，繼續進行別的狀態轉移用 `check(r, c)` 檢查將皇后放置在 $(r, c)$ 後是否能繼續再放置其他皇后。用點幾何概念的話，會發現 `check()` 只需要 $O(N = 8)$ 就能做到： ```cpp bool check(r2, c2) { for (int r1 = 0; r1 < r2; r1++) { int c1 = board[r1]; if (c1 == c2 || c1-c2 == r1-r2 || c1-c2 == r2-r1) return false; } return true; } ``` 枚舉的盤面會少於 $N!$ 很多，因為 `check()` 剪掉了許多不必再繼續遞迴下去的 DFS 樹枝。 ![](https://blogs.mathworks.com/steve/files/queen-solver-animation-6.gif)[^bt-2] #### 練習： [UVa OJ 524 Prime Ring Problem](https://uva.onlinejudge.org/external/5/524.pdf) [UVa OJ 211 The Domino Effect](https://uva.onlinejudge.org/external/2/211.pdf) [^7]: 看英文 walk 這字，帶有一種隨意的感覺，是種無限制的路 [^8]: 很多人無法很好的區分道路與路徑，甚至行跡，通常得仔細讀上下文 [^10]: 這邊容易誤會，因為 disjoint sets tree 的"根"，是我們進行遞迴下探走到的"葉"。 [^convention]: 這個變數將成為以後的慣例 [^dfs-1]: 注意，這裡的圖剛好是連通的。 [^dfs-2]: [State space search](https://en.wikipedia.org/wiki/State_space_search) [^bfs-1]: 有時間可以玩玩看 [pipes](https://github.com/ccns/105-club-fair-game-problems/tree/master/1/2)，裡頭有附上 source code [^bt-1]: [Wikipedia/ Eight queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle) [^bt-2]: [Mathworks/ The Eight Queens Problem](https://blogs.mathworks.com/steve/2017/04/20/the-eight-queens-problem/) [^CE]: 不過實驗證明，提交上 Codeforces 會拿到 Compilation error [^combination]: 就是組合 $C$ $64$ 取 $8$ 的意思

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.