題目： UVa - 924 - Spreading The News 題目說明在一個組織裡面散布消息，組織裡面的員工都有跟自己比較好的朋友，每位員工收到消息後會在隔天跟所有比較好的朋友說，現在將消息告訴一位員工，求在哪一天消息會被最多原本不知道的人知道。 Input： 不太好解釋，所以直接拿題目的 Sample I/O 來解釋。 12345678910116 表示有 6 位員工 ( 序號為 0 ~ 5 )2 1 2 第零位員工的朋友，第一個整數為朋友數，後面接的是朋友的序號，意思為，若 0 號收到消息，會在隔天跟 1 號還有 2 號說2 3 4 第一位員工的朋友，第一個整數為朋友數，後面接的是朋友的序號，意思為，若 1 號收到消息，會在隔天跟 3 號還有 4 號說3 0 4 5 .1 4 .0 .2 0 2 第一位員工的朋友，第一個整數為朋友數，後面接的是朋友的序號，意思為，若 5 號收到消息，會在隔天跟 0 號還有 2 號說3 幾組測試0 若先將消息跟 0 號 ...

題目： UVa - 429 - Word Transformation 題目說明給一些在字典裡面的字串，在這些字串中，若兩個字串只相差了一個字元，就可以進行轉換，給原本的字串跟目標字串，求轉換幾次後能得到目標字串。 Input： 第一行為一整數 T，代表有 T 組測資，後面接一個空行，之後每行會有一個字串，代表字典裡面的字，直到讀到 "*" 為止，之後每行會有兩個字串，分別代表原本的字串跟目標字串，直到讀到空行為止。空行後就是下一組測資。 Output： 輸出原本的字串及目標字串，及轉換的次數 ( 題目應該是保證會有答案 )。 解題思路可以透過建圖，將題目的問題轉換成最短路徑的問題，先讀取測資，並將字串兩兩判斷，若兩字串只相差一個字元就建邊 ( 注意這裡要建雙向，因為兩者可相互轉換 )，之後讀取原本的字串跟目標字串，從原本的字串開始 BFS 求解即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555 ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-11-26截止時間：2020-12-03 題目說明這次的作業是 UVa 中的 3 題題目。與 Strongly Connected Components 相關。 UVa - 247 - Calling Circles：UVa - 247 解題紀錄 UVa - 11504 - Dominos：UVa - 11504 解題紀錄 UVa - 11838 - Come and Go：UVa - 11838 解題紀錄

題目： UVa - 11838 - Come and Go 題目說明給有向圖，求整張圖是否為一個 SCC ( Strongly Connected Component )。SCC 即在有向圖上任意選兩點 u、v，u 能夠走到 v 且 v 也能夠走到 u。 Input： 每組測資第一行為兩個整數 N、M，分別代表 點的數量 (1 ~ N) 及 邊的關係，若 N、M 都為 0 則結束。接下來 M 行每行有三個整數 u、v、P，若 P 為 1 表示有 u -> v 的邊，若 P 為 2 表示有 u -> v 及 v -> u 的邊。 Output： 若整張圖為一個 SCC 則輸出 1，否則輸出 0。 解題思路DFS 找 SCC 並紀錄 SCC 的個數即可。需要注意的是當我們知道 SCC 的個數大於一就可以直接輸出了不用繼續往下做。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 ...

題目： UVa - 11504 - Dominos 題目說明給一些骨牌的相對關係，求最少需要推倒幾個骨牌才能使得所有骨牌都倒下。 Input： 第一行為一整數 T，表示總共有 T 組測資，每組測資的第一行為兩個整數 n、m，代表有 n 個骨牌 ( 序號為 1 ~ n )，及 m 個相對關係，後面 m 行每行會有兩個整數 u、v，表示若 u 倒下則 v 也會倒下。 Output： 輸出最少需要推倒幾個骨牌才能使得所有骨牌都倒下。 解題思路其實就是找 SCC ( Strongly Connected Component )，SCC 即在有向圖上任意選兩點 u、v，u 能夠走到 v 且 v 也能夠走到 u。因此我們在 SCC 中任意推倒一個骨牌就能使得整個 SCC 都倒下，之後把每個 SCC 都當成一個點 ( 即縮點的概念 )，之後找出每個 SCC 被幾個其他的 SCC 所接入，如果 SCC 有被其他的 SCC 接入，表示只要推倒那個 SCC，這個 SCC 也會被推倒，最後看有幾個 SCC 沒有被接入即是答案。 參考解法1234567891011121314151617181920212 ...

題目： UVa - 247 - Calling Circles 題目說明有一家電信公司記錄了所有人之間打電話的紀錄，他們想找出所有的通話圈圈 ( Calling Circles )舉例來說，如果 A 打給 B，B 打給 C，C 又打給 A，A、B、C之間就可以跟任何一個人互相溝通，他們就形成一個 Calling Circle。但假如 D 可以打給 A，但 A 不能打給 D，D 跟 A 就不算 Calling Circle。 Input： 每筆測資先給你總共的人數 n，和通話紀錄 m 筆，接下來 m 行會有兩個人名 ( 25字元以內 )，代表前面的人可以打給後面的人 ( 單向 )。 Output： 每筆測資先輸出一行 “Calling circles for data set x:” ( x 代表第幾筆 )，接下來每行輸出一個 Calling Circle 中的所有人名，之間以逗號和空白隔開，順序都可以。 引用自：愚人隨筆: UVA 247 - Calling Circles 解題思路題目的 Calling Circles 其實就是 SCC ( Strongly Connected ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-11-21截止時間：2020-11-28 題目說明這次的作業是 UVa 中的 5 題題目。三題與 Articulation Points / Bridges 相關，兩題與 Biconnected / Bridge Connected Components 相關。 與 Articulation Points / Bridges 相關 UVa - 315 - Network：UVa - 315 解題紀錄 UVa - 796 - Critical Links：UVa - 796 解題紀錄 UVa - 10765 - Doves and bombs：UVa - 10765 解題紀錄 與 Biconnected / Bridge Connected Components 相關 UVa - 1108 - Mining Your Own Business：UVa - 1108 解題紀錄 UVa - 10972 - RevolC FaeLoN：UVa - 10972 解題紀錄

題目： UVa - 10972 - RevolC FaeLoN 題目說明給一個無向圖，現在要把圖轉換成有向圖，且邊可以任意定向 ( 即原本邊 (u, v)，可以變為 u -> v 或 v -> u )。求需要加幾條邊才能使得轉換後的圖形為強連通 ( 即在有向圖上任意選兩點 u、v，u 能夠走到 v 且 v 也能夠走到 u )。 Input： 每組測資的第一行為兩個整數 n、m，分別代表 點的數量、邊的數量，後面 m 行每行有兩個整數 u、v，表示圖上有邊 (u, v)。 Output： 輸出最少需要加幾條邊使得圖轉換成有向圖後會是強連通。 解題思路我們可以發現，無向圖中的 Bridge Connected Component ( 以下簡稱 BCC，注意不是 Biconnected component )，在把邊任意定向後一定可以變成一個強連通分量，原因在於強連通分量其實類似於無向圖中的環，詳細說明可參考本篇文章：【RevolC FaeLoN Uva 10972】 - 大米饼 - 博客园。 所以可以得出圖上 BCC 內的點其實不影響我們求解的結論，因此我們把圖上的所有 B ...

題目： UVa - 1108 - Mining Your Own Business 題目說明給一個連通的無向圖，求最少在圖上標記幾個點，使得圖上任意一點崩塌 ( 被拿掉 ) 後，其他所有的點都能夠走到被標記的點。 Input： 每組測資起始於一整數 N，若 N 為 0 代表結束，否則下面 N 行，每行會有兩個整數 u、v，表示圖上有邊 (u, v)。 Output： 輸出最少需要標記的點及標記點的方法數。 解題思路解這道題首先需要求出 Binconnected component ( 以下簡稱為 BCC )，因為在 BCC 上拿掉任意一點都不會打破原本的連通性 ( 因為 BCC 上沒有割點 )，之後我們可以發現，因為原本圖是連通的，所以我們只需要在 只有連接到另一個 BCC 的 BCC 上有標記點即可，因為若一個 BCC 連接到兩個以上的 BCC，則在整張圖上拿掉任意一點，在這個 BCC 上的點都可以走到其他的 BCC 上被標記的點。我們也可以發現，雖然標記在割點上能使得連接到的 BCC 都能走到，能夠達到標記最少的點，但是若被拿掉的是割點則會打破原本連通性的導致連接到的 BCC ...

題目： UVa - 10765 - Doves and bombs 題目說明其實我不是太懂題目的意思，就以我理解的想法大致敘述一下。 給一個圖，求在圖上任意拿掉一點使得原本該點所在的連通圖會被分為幾個連通圖 ( 意思為在一個連通圖上拿掉一點，使得該連通圖被分為幾個連通圖 )，輸出前面幾個拿掉會造成原本的連通圖被分為最多個連通圖的點及連通圖的數量。 Input： 每筆測資的第一行為兩整數 n、m，n 表示圖上有 n 個點 (0 ~ N - 1)，若 n 及 m 皆為 0 代表結束。接下來每行會有兩個整數 u、v 表示邊 (u, v) 是連通的，若 u、v 皆為 -1 代表結束。 Output： 輸出前 m 大的結果 ( 值較大的在上面，若值相等則序號較小的在上面 )。 解題思路先讀取測資並建圖，之後 DFS，紀錄 DFS 時的序號及 low 值 ( 記錄節點 u 或 u 的子樹通過非父子邊追溯到最早的祖先節點 ( 即 DFS 的序號最小 ) )，之後根據割點的定義，紀錄每個點被多少個點視為割點最後再加一即為該點的值，因為若一個點被另一個點視為割點，則該點拿掉的話會導致原本的連通圖變為 ...