這是本學期高等演算法最後一次(第四次)作業，去年我修課時，阿喜老師有提到，我覺得相當有趣，不過當時他出了台北捷運路線圖的題目，做完之後很有成就感，因為可以把所學用在日常生活上。今年阿喜老師真的把成語接龍當作作業了！
首先以十個成語為例子，它們可以連結的關係如下：
- 最短的成語接龍：天人合一 一手遮天 天無二日 日暖風和 和風細雨 雨過天青
- 最長的成語接龍：天人合一 一手遮天 天無二日 日復一日 日甚一日 日暖風和 和風細雨 雨過天青
- 包含特定成語的Strongly connected components：天人合一 一手遮天 一步登天
接著給定7017個成語的資料庫，並且做以下三個測試：
測試例子（頭->尾）
- 天人合一 雨過天青
- 曠日持久 星月交輝
- 無孔不入 投機倒把
最短：
- 4 (天人合一 一倡百和 和風細雨 雨過天青)
- 7 (曠日持久 久仰大名 名符其實 實話實說 說一是一 一路福星 星月交輝)
- 5 (無孔不入 入不敷出 出其不意 意氣相投 投機倒把)
最長：
- 1582/1384
- 1587/1372
- 1573/1368
包含特定成語的Strongly connected components：
- 3812
- 1
- 3812
最短和包含特定成語的Strongly connected components沒有特別的問題，然而最長序列因為是NP問題，所以無法在線性時間內找出解來，因此同學們的答案有很大的出入，然而我核對比較厲害的同學的答案，最長序列前兩名的長度如上。
成語接龍之最長序列很有趣，第一長的同學程式執行時間將近700秒，而第二長的同學則不到1秒即跑出結果，用時間換取精確值看來最為有利！並不是很快就求出結果的人是最厲害的！快、狠、準三者，先求準，再來求快！若所求不對，再快也枉然！要狠得化就用最簡單又令人驚奇的作法，實在不需要複雜化問題。
第一長的同學所用來測量的軟硬體規格：
- CPU : Intel Core 2 Quad Q6600 (2.4GHz * 4)
- RAM : 8GB
- OS : Windows 7 Ultimate SP1 (x64)
- IDE : Visual Studio 2008 SP1
他所得到的測試時間（亂數取十組成與來做測試）：
由於7017個成語太多，不在此列出來，而最長序列只列出部份如下：
- 天人合一 一了百當 當局者迷 迷迷糊糊 糊裡糊塗 … 老成持重 重新做人 人仰馬翻 翻雲覆雨 雨過天青
- 曠日持久 久旱不雨 雨沐風餐 餐風宿水 水乳交融 … 整齊劃一 一元復始 始終如一 一路福星 星月交輝
- 無孔不入 入木三分 分憂解勞 勞燕分飛 飛蛾赴火 … 有何不可 可有可無 無聲無臭 臭味相投 投機倒把
Strongly connected components的定義：A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a.
直接看圖比較好懂：
簡單來說，淺藍色部份都是Strongly connected components，選定某兩個節點，此兩個節點各有路徑可以來回，如a→b，b→a。
所測試得到Strongly connected components有3812個成語挺多的！如果有同學把它們的關係畫成圖示，讓我一目了然的話，我一定給他滿分！用程式具現化應該很容易才對～
話說，當課程助教的好處是，可以發現很厲害的同學，然後跟他學習！還能拿高手的程式來執行和修改，未來想必多少都可以派上用場呢！
參考：WiKi – Strongly connected component、演算法筆記 – Connectivity。
逍遙文工作室 
隨意留個言吧：）～