用C++解决单词接龙的最长龙问题

Question

1.首先我们定义单词接龙的规则是：
1）后一个单词的首字母，会等于前一个单词的末尾的字符；
2）每个单词只能出现1次；
3）如果最长龙是有多个长度都一致，给出所有可能的接龙结果。
请写一个程序，那么在随意输入N个单词（单词与单词之间用空格分割，用回车表示结束）后，程序能够给出可能最长龙的接龙结果。
举例：
输入：arachnid aloha dig rat tiger gopher
系统输出：aloha arachnid dog gopher rat tiger

Answer 1

用有向图的数据结构，每个节点代表一个单词，把能接上的两个单词用箭头连起来。 这个时候问题就变成了找该有向图的最长路径，这个算法有很多，如果问题变成是否所有单词能连成一条龙，则就是找该有向图的哈密顿通路的问题。