poj 1386

题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）

思路：欧拉路。

关于欧拉路：

(1)**有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。**

(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。

阅读更多