題目： UVa - 796 - Critical Links 題目說明給一個無向圖，求 Bridge 的數量 及 Bridge。 Bridge 的定義： 對於一個連通的無向圖來說，若拿掉某一邊會導致原本連通的圖變得不連通，則該邊為 Bridge。 對於任意邊 (u, v)，若 v 及 v 的 descendant 不存在一條連接到 u 的 ancestor 的 Back edge，則 (u, v) 為 Bridge。 Input： 每組測資的第一行為一整數 N，表示圖有幾個點 (0 ~ N - 1)，接下來 N 行為每個點的連接情況，第一個數字為該點，後面接一個用左右括號括起來的數字 n，表示連接到 n 個點，後面 n 個數字為連接到的點，中間都以空格隔開。 Output： 輸出 Bridge 的數量及 Bridge。Bridge 要求輸出時是小的點連接到大的點 ( 如 (1, 5) 需輸出為 "1 - 5"，不可輸出為 "5 - 1" )，並且先依照前面的數字小到大排序，若前面一樣則依照後面的數字小到大排序 ( 即為 pair 的比 ...

題目： UVa - 315 - Network 題目說明給一個所有點都有接通的無向圖，找出 Articulation Points ( 也叫 Cut Vertex、割點 ) 的數量。 Articulation Points 的定義： 對於根節點 root，若其有兩棵或兩棵以上的子樹 ( degree >= 2 )，則該根節點 root 為割點。 對於非葉子節點 u ( 非根節點 )，若其 child 存在一個節點 v 或 v 的 descendant 沒有指向 u 的 proper ancestor ( 不包含 u ) 的 Back edge，則節點 u 為割點。 Input： 每組測資的第一行為一整數 N，表示有 N 個節點，若 N 為 0 代表結束，接下來最多 N 行為以空格隔開的數字，若為 0 則代表這筆測資結束，否則代表邊。如 5 1 2 3 4 表示有 ( 5, 1 )、( 5, 2 )、( 5, 3 )、( 5, 4 ) 這些邊。 Output： 輸出 Articulation Points 的數量。 解題思路先讀取測資並建圖 ( 因為是無向圖，所以建雙向 ...

課程名稱：線性代數 CS233 B授課教師：簡廷因發放時間：2020-11-02截止時間：2020-11-30 23:59:59 題目說明給一張圖片 ( jpg )，偵測出圖片中最長的直線，逆時針旋轉直到直線垂直於水平線，並將旋轉後多出來的部份塗黑，之後輸出成圖片檔 ( jpg )。 本次作業可使用 OpenCV 套件 參數設定： Canny 使用 500，100HoughLinesP 使用 1, CV_PI / 180, 250, 200, 10 OpenCV 設定在Visual Studio 2019上使用OpenCV : 先依照這篇設定，之後會遇到錯誤類似於 LNK1104 無法開啟檔案 'opencv_world401d.lib'[圖文] OpenCV 4.0.1 安裝配置在 Visual Studio 2019 : 之後再依照這篇設定環境參數即可。 解題思路先使用 imread() 讀取圖片，之後使用 Canny() 完成邊緣偵測，再使用 HoughLinesP() 完成霍夫直線判斷，得到圖片中所有直線的陣列，之後遍歷陣列取得最長邊的斜率 ( 長度可使用 n ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-11-05截止時間：2020-11-12 題目說明這次的作業是 UVa 中的 6 題題目。三題與 DFS 相關，三題與 Topological Sort 相關。 與 DFS 相關 UVa - 168 - Theseus and the Minotaur：UVa - 168 解題紀錄 UVa - 11906 - Knight in a War Grid：UVa - 11906 解題紀錄 UVa - 12442 - Forwarding Emails：UVa - 12442 解題紀錄 與 Topological Sort 相關 UVa - 200 - Rare Order：UVa - 200 解題紀錄 UVa - 872 - Ordering：UVa - 872 解題紀錄 UVa - 10305 - Ordering Tasks：UVa - 10305 解題紀錄

題目： UVa - 10305 - Ordering Tasks 題目說明給一整數 N 代表有 N 個任務要完成，及 M 個規則，表示在做某個任務前需要完成的任務。求適合的執行任務順序 ( 符合規則即可 )。 Input： 每組測資第一行為兩個整數 N、M，若 N、M 皆為 0 表示結束。否則接下來 M 行，每行都有兩個整數 a、b，表示在做任務 b 前需要先完成任務 a。 Output： 符合規則的任務執行順序。 解題思路基本的 Topological sort，建圖之後做 DFS 即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>#include <functional>#include <vector>#include <list>using namespace std;#define LOOP(n) for(int ...

題目： UVa - 872 - Ordering 題目說明給一些字母，及一些規則，如 A < B，表示 B 一定要排在 A 後面。求符合規則所有排序情況，並依照字典序輸出。 Input： 第一行為一整數，代表有幾組測資，每組測資的第一行為所有字母 ( 中間以空格隔開 )，第二行為排序規則 ( 一定是 < 的形式，中間以空格隔開 )。每組測資中間以空行隔開，整數及第一筆測資間也以空行隔開。 Output： 輸出所有排序情況並按照字典序排序。 解題思路讀取所有字母並按照字典序排序 ( 確保後面做 DFS 時先輸出的會是字典序較小的 )，之後讀取規則，將 G[A][B] 設為 1 表示 A 指向 B，…，以此類推來建圖，之後 DFS 做 Topological Sort，同時搭配 Back Tracking 來排出所有情況即可。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 ...

題目： UVa - 200 - Rare Order 題目說明給一些依據某種字典序排序的字串，求該字典序為何。 Input： 測資裡面有好幾行字串，以 "#" 為終止，字串的順序為升冪排序。 Output： 輸出測資以什麼字典序排序。 解題思路讀取測資，每次取兩個字串來比較，將比字元 A 大的字元推入 G[0] 表示 A 指向該字元，…，以此類推來建圖，同時使用一個陣列紀錄字元的狀態，因為 DFS 時需要以沒有大於其他字元的為起點，之後使用 DFS 做 Topological sort 即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <iostream>#include <algorithm>#include <functional>#include <vector ...

題目： UVa - 12442 - Forwarding Emails 題目說明有一個小鎮，裡面的居民每個人都只會給另一個人寄信，求把信寄給哪位居民可以讓最多人看到這封信，若有相同者則取較小者。 Input： 第一行為一整數 T，代表有 T 組測資，每組測資的第一行為一整數 N，接下來 N 行每行都有兩個整數 u、v，代表居民 u 會把信寄給居民 v。 Output： 輸出寄信給誰可以讓最多的居民看到這封信，若有相同者則取較小者。 解題思路DFS 模擬即可，由於會 TLE，所以進行一點剪枝，多使用一個陣列紀錄某位居民是否已經被模擬過了，若在前面被模擬過了則就不需要在模擬第一個寄信給這位居民了，因為前面模擬的是另一個居民會寄給這位居民，一定會比直接寄信給這位居民的人數還要多。例如： 12345678若居民有 3 人，且寄信關係為：1 32 33 2則寄信給第一位居民時會再寄給第三位居民，那遍歷到第三位居民時就不需要在模擬一次了，因為由第一位寄給第三位，一定會比直接寄給第三位多。 參考解法123456789101112131415161718192021222324252627282 ...

題目： UVa - 11906 - Knight in a War Grid 題目說明有一個騎士在一個 R x C 的棋盤上移動，從 (0, 0) 開始，每次可以從該點移動到 (±M, ±N) 及 (±N, ±M) 的點，有些點有水則不能跳。如果一個點能從偶數個點跳過來則標記為 偶，如果能從奇數個點跳過來則標記為 奇。求整個棋盤上 奇 跟 偶 的個數。 Input： 第一行為一整數 T，代表有 T 組測資，每組測資的第一行為 4 個整數 R、C、M、N，接下來一行為一個整數 W，代表有 W 個有水的點，接下來 W 行，每行有兩個整數，代表有水的點的座標 **(x, y)**。 Output： 輸出每組測資的 偶、奇 個數。 解題思路使用 DFS 模擬，紀錄每個點被走到的次數，最後再計算 奇、偶 的個數即可，需要注意的是若 M、N 皆大於 0 且不相同，每次會有 8 個點可以走，若 M、N 相同或是兩者中有一個為 0 則每次只會有 4 個點可以走。還有若是 (0, 0) 除了一開始走到之外都沒有被走到的話會被歸類在 even 裡面。 參考解法123456789101112131415 ...

題目： UVa - 168 - Theseus and the Minotaur 題目說明有一個迷宮，一個勇者跟一個怪物，怪物會怕光，所以勇者拿著蠟燭在追逐怪物，勇者每走一定的步數後會插上蠟燭，並繼續走，所以怪物一定會被逼到無路可走，求勇者有插上蠟燭的地方及最後怪物被抓到的地方。在每個地點怪物都會優先往字典序小的地方走。 Input： 一組測資為一行字串，前面為每個地點能繼續往下走的地點 ( 單向 )，後面為兩個字元及一個數字，分別代表怪物一開始的位置及勇者一開始的位置及勇者每走幾步會插上蠟燭。勇者一開始一定會在怪物的附近一個點。 Output： 勇者插上蠟燭的地方及怪物最後被抓到的地方。 解題思路讀取資料後先建立圖，遍歷字串，若碰到 ':' 代表前面一個字元為某個地點，後面接的是某個地點能繼續往下走的地點，直到遇到 ';' 或 '.' 為止。定義 candle 紀錄插上蠟燭的位置，steps 為勇者走的步數，M 為怪物當前的位置，T 為勇者當前的位置，之後 DFS 求解即可，先判斷是否插上蠟燭，接著找怪物能繼續往下走的位置，若有可以 ...