# 題目: UVa 10188 - Automated Judge Script # 題目說明 程式競賽的評審很嚴格但又很懶散，他們希望能少一點工作及多一點錯誤答案 你需要寫一個自動化的評審系統，根據標準答案及回答，給出: Accepted、Presentation Error、Wrong Answer其中之一 Accepted : string中所有字元皆相同 Presentation Error : 所有數字皆正確，但至少有1個以上的字元錯誤 Wrong Answer : 數字錯誤 INPUT: 每筆資料第一行有一個整數N，代表接下來有幾行標準答案 接下來輸入N個string 當N

# 題目: 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

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

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

# 題目: 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的數量及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, 4) OUTPUT: 輸出Articulation P

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

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

# 題目: UVa 10557 – XYZZY # 題目說明 給一張有向圖，每個點都有能量變化(可能正可能負)，起點為100能量 求起點是否能走到終點 INPUT: 每筆測資第一行有一個整數n，代表有n個點，若n = -1結束程式 接下來有n行，依序為1 ~ n個點的資訊，每行至少有兩個整數val、j val代表該點的能量消耗 j代表接下來有j個整數，該點連接到這些整數 OUTPUT: 從起點(1)能走到終點(n)輸出winnable，否則輸出hopeless # 解題方法 因為題目為能量消耗，所以我們要找最大路徑 當有正環發生時，若該點能走到終點，則能量無限，直接輸出win

# 題目: 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演算法找到最短路徑，若還能找到更短的邊則有負環 # 參考程式碼 #include <iostream> #include &#x