# 題目: UVa 10050 - Hartals # 題目說明 題目給總天數及各個 party 的間隔天數 天數從禮拜天開始算，禮拜天為 day 1 周五及周六不算 求 hartal 的天數 例如: 天數 N = 9 ， party1 = 3 、 party2 = 4 星期 日 一 二 三 四 五 六 日 一 天數 day1 day2 day3 day4 day5 day6 day7 day8 party1 o o o party2 o o hartal 1 2 3 4 hartal = 4 INPUT: 第一行為一個整數 T...

# 題目: UVa 673 - Parentheses Balance # 題目說明 有一個包含 [ 、 ] 、 ( 、 ) 這四種符號的字串，你需要判斷此字串是否符合以下規則 空字串為 correct 如果 A 與 B 皆為 correct ， AB 為 correct 如果 A 為 correct ，那 [A] 與 (A) 也為 correct INPUT: 第一行為一個整數 T ，代表有幾筆資料 每筆資料輸入一串字串 OUTPUT: 結果為 correct 輸出 Yes ，否則輸出 No # 解題方法 使用 stack 當輸入為 ] 、 ) 時，判斷 stack.top() 是否為...

# 題目: UVa 10765 - Doves and Bombs # 題目說明 給一個無向圖，當拿掉一個割點時，此圖會分成數個連通圖 求前 m 個可以分為最多連通圖的點及連通圖的數量 INPUT: 每筆測資第一行有兩個整數 n 、 m ，當 n 、 m 為 0 時結束 n 代表節點數 m 代表輸出 m 筆結果 (降冪排序) 接下來每行有兩個整數，代表兩整數存在一條邊連通 當兩整數為 -1 時結束 OUTPUT: 輸出前 m 筆結果 (降冪排序) # 解題方法 先建圖，建雙向邊 之後跑 dfs ，紀錄每個點的 dfn值 及...

# 題目: UVa 796 - Critical Links # 題目說明 給一個無向圖，求 bridge 的數量及 bridge 為哪兩個點連接 bridge 定義: 一個連通圖，若拿掉一個邊會使此圖不連通，則此邊為 bridge 對於任意邊，一點不存在連通至 ancester 的 backedge ，則此邊為 bridge INPUT: 每筆測資第一行有一個整數 N ，代表有 N 個節點 (0 ~ N-1) 接下來有 N 行，每行第一個數字為該點，括號刮起來為連到的節點數 例如 2 (2) 1 3 代表有兩個邊 (2, 1)、(2, 3) OUTPUT: 輸出 bridge 的數量及...

# 題目: UVa 315 - Network # 題目說明 給一個點皆連通的無向圖 求 割點(Articulation Points 的數量 割點定義: 對於 root ，如果 root 有兩顆以上的 subtree ，那 root 為割點 對於非 leaf 的其他節點，其 child 沒有一條 back edge 指到 ancester ，則該點為割點 INPUT: 每筆測資第一行有一個整數 N ，代表有 N 個節點 當 N = 0 時結束程式 接下來有最多 N 行，每行有數個整數 例如 5 1 2 3 4 代表有四個邊 (5, 1)、(5, 2)、(5, 3)、(5,...

# 題目: UVa 10305 - Ordering Tasks # 題目說明 給 n 件事及 m 個規則，求符合的順序 INPUT: 第一行有兩個整數 n 、 m ，代表有 n 件事要做，有 m 個規則 接下來有 m 行，每行有兩個整數，代表要先做前者才能做後者 OUTPUT: 符合規則的做事順序 # 解題方法 先建圖，將後者先標為 true 之後跑 dfs ，將走過的點設為 true 並 push 到 result # 參考程式碼 #include <iostream>#include <memory.h>#include...

# 題目: UVa 872 - Ordering # 題目說明 題目給數個字母及排列順序 求所有的可能排序 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 接著有兩行字串，第一行為所有的字母，第二行為這些字母的排列順序 每個字母間以空格隔開 OUTPUT: 輸出所有可能的字母排序 # 解題方法 以字串儲存字母並排序 接著跑 dfs ，判斷字母是否有跑過、是否符合規則，都是則繼續跑下一層 dfs # 參考程式碼 #include <iostream>#include <string>#include...

# 題目: UVa 10557 – XYZZY # 題目說明 給一張有向圖，每個點都有能量變化 (可能正可能負)，起點為 100 能量 求起點是否能走到終點 INPUT: 每筆測資第一行有一個整數 n ，代表有 n 個點，若 n = -1 結束程式 接下來有 n 行，依序為 1 ~ n 個點的資訊，每行至少有兩個整數 val 、 j val 代表該點的能量消耗 j 代表接下來有 j 個整數，該點連接到這些整數 OUTPUT: 從起點 ( 1 ) 能走到終點 ( n ) 輸出 winnable ，否則輸出 hopeless #...

# 題目: UVa 558 - Wormholes # 題目說明 給一張有向圖， n 個點透過 m 條邊相連，每個邊有 weight 求圖上是否有負環 INPUT: 第一行有一個整數 T ，代表有幾筆測資 每筆測資第一行有兩個整數 n 、 m ，代表有 n 個點及 m 條邊 接下來有 m 行，每行有三個整數 u 、 v 、 w ，代表點 u 連接到點 v (單向) 且 weight 為 w OUTPUT: 有負環輸出 possible ，無則輸出 not possible # 解題方法 先建圖 接著以 bellman 演算法找到最短路徑，若還能找到更短的邊則有負環 #...

# 題目: UVa 10449 - Traffic # 題目說明 給一個有向圖，圖中每個點皆有值，而從一個點移動到下一個點的 cost 為 (目的點的值 - 當前點的值) * 3 求 1 到終點的最短路徑 INPUT: 每筆測資第一個輸入為整數 n ，代表有 n 個點 接下來有 n 個整數，代表從 1 ~ n 的點的值 第二行有一個整數 m ，代表有 m 條邊 接下來有 m 行，每行有兩個整數，代表前者連接到後者 (單向) 最後有一個整數 q ，代表終點的數量 之後 q 個整數代表終點的位置 OUTPUT: 輸出從 1 到終點的最短路徑 如果最短路徑或無法找到，則輸出 ? #...