UVa 247 – Calling Circles

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=183

 

將這些通話紀錄建成一張有向圖，則一個Calling Circles就是這張圖的一個強連通元件(SCC)，這裡使用Kosaraju演算法找SCC。

UVa 11504 – Dominos

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2499

這題其實用自己玩骨牌的經驗去想還蠻好懂的，只不過玩骨牌不會去想那麼多就是了~~~如果有一群骨牌的關係是，不管推倒哪一個，這一群的其他骨牌都會倒，那可以把這一群骨牌看成一體，用圖的角度去分析，這一群骨牌就是一個強連通元件(SCC)。所以這題我先用Tarjan演算法求SCC，並把每一個SCC縮成一個頂點，接下來再由新產生的這張有向無環圖(DAG)，去找入度為0(也就是沒有邊連入)的頂點有多少個，這個數字即代表最少必須推幾個骨牌才能讓全部骨牌倒。而求SCC時我使用的是Tarjan演算法。

有向圖的強連通元件Strongly Connected Component

強連通元件(Strongly Connected Component)

在一張有向圖中，如果任兩個不同頂點a、b雙向都存在路徑時(即從a可以到b、從b可以到a)，我們稱這個圖為強連通圖。一個強連通元件(SCC)指的是一張有向圖G中的極大強連通子圖G’。

(取自演算法筆記)