[問題] 最長成語接龍

[noodleT (麵T)]

給定 n 個不重複的成語，
如何在這些成語中找出一個最長的成語接龍？

如果有多組答案，只要輸出其中一組即可。

請問複雜度降到多項式時間的可能嗎？
實在沒有什麼想法…

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.9.252
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1477729199.A.406.html
→ pttworld: LIS方向可能。
→ sifmelcara: 最長路徑是NP-hard
→ noodleT: 如何證明 NP hard
→ yr: 轉成 directed graph ， longest path problem 為 NP-hard
→ FRAXIS: 最長的定義是什麼？ 可以用重複成語的話可以無限長吧
→ noodleT: 不能重複使用、利用最多成語為最長