poj 1386 Play on Words (欧拉路)

poj 1386

题意:n个单词,问能否形成一个串(单词接龙,收尾相连,当且仅当前一个单词的末尾字母和后一个单词的首字母相同)

思路:欧拉路。

关于欧拉路:

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

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

(3) 无向图存在欧拉回路:  图连通,所有点都是偶数度,

(4)无向图存在欧拉路:图联通,只有两个点的度数为奇数。

有向图判断联通性判断的弱联通,因此可以用并查集实现。

具体办法是,判断根的个数,个数为大于1表示不联通。

 

 

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz