poj 1386 题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同） 思路：欧拉路。 关于欧拉路： (1)**有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。** (2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。 （3） 无向图存在欧拉回路: 图连通，所有点都是偶数度， （4）无向图存在欧拉路：图联通，只有两个点的度数为奇数。 有向图判断联通性判断的弱联通，因此可以用并查集实现。 具体办法是，判断根的个数，个数为大于1表示不联通。 …