UVa 10129

Play on Words

from Volume 2. Data Structures :: Graphs

Description

输入一些单词，要求把这些所有的单词都用成语接龙的办法连起来。输出可能或者不可能。

Solution

对于每个单词，有价值的就是第一个单词和最后一个单词。虽然输入数据可能高达100000个，但是字母只有26个。可以以这些字母为点，把这题的模型化为有向图。然后题目所求的就是这无向图的一个欧拉路径。要求欧拉路径，可以计算每个点的入度和出度，容易理解除了第一个单词开头的字母，和最后一个单词结尾的字母，其他的字母入度和出度必然相等。而第一个单词开头的字母和最后一个单词结尾的字母，前者入度比出度大一，后者出度比入度小一。不过要记得，当所有点的入度和出度都相等，即构成欧拉回路，也符合题目的要求。最后别忘了这个定理成立的条件——这个图的无向图，必须是连通的。DFS 一下某个点的连同分支是否可以到达每个点即可。