UVa 12238 – Ants Colony

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

最近共同祖先(Lowest Common Ancestor，LCA)定義為在一棵樹上，兩個節點u和v，它們離根節點最遠的也就是深度愈低的共同祖先，只有唯一一個。

這題要求任意兩點間的最短路徑，但是因為N太大，所以Floyd-Warshall最短路徑演算法就沒辦法了，而這題有保證這張圖是一棵樹，因為任一兩點u和v之間的最短路徑，以樹來看一定會經過他們的LCA，所以可以得到u和v最短路徑就是dist(root, u) + dist(root, v) – dist(root, LCA(u,v)) * 2，實際畫畫看很好懂。

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演算法。