Poj 1386欧拉回路
题意：如果单词A的结尾字母与单词B的首字母相同，那么可以认为是A到B相通。给出一系列单词，求这些词按照某种排列能否串通。题解：如果直接按照题意建模，以单词为顶点，边表示两两相通，那么将会得到哈密顿回路模型。显然是很难解的。换一种方式，以字母为顶点，边表示传送的单词，那么就得到欧拉回路模型的图，可以按照欧拉定理求解。以下给出Euler图的相关知识：Euler回路：G中经过每条边一次且仅一次的回路Euler路径：G中经过每条边一次且仅一次的路径无向图存在Euler回路定理：当它是连通图+顶点度数为偶数无向图存在Euler路径定理：当它是连通图+除两个顶点度为奇数外，其余为偶数有向图存在Euler回路定理：当它是连通图+顶点入度 == 出度有向图存在Euler路径定理：当它是连通图+除一个顶点的入度和出度的差的绝对值小1外，其余相等代码： #include &stdio.h&#include &string.h&const int N = 30;
class UnionSet{private:&&& int parent[N];&&& int rank[N];&&&public:&&& UnionSet(int _size):size(_size)&&& {&&&&&&& init();&&& }&&& ~UnionSet()&&& {&&& }
&&& void init()&&& {&&&&&&& for(int i = 0; i & ++i)&&&&&&& {&&&&&&&&&&& parent[i] = -1;&&&&&&&&&&& rank[i] = 1;&&&&&&& }&&& }
&&& int root(int _x)&&& {&&&&&&& int r = _x;&&&&&&& while(parent[r] &= 0)&&&&&&&&&&& r = parent[r];&&&&&&& int i = _x;&&&&&&&&&&&&&& while(parent[i] &= 0)&&&&&&& {&&&&&&&&&&& j = parent[i];&&&&&&&&&&& parent[i] =&&&&&&&&&&& i =&&&&&&& }&&&&&&&&&& }
&&& int Union(int _r1,int _r2)&&& {&&&&&&& if(_r1 == _r2)&&&&&&&&&&& return _r1;&&&&&&& else&&&&&&& {&&&&&&&&&&& int root1 = root(_r1);&&&&&&&&&&& int root2 = root(_r2);&&&&&&&&&&& if(root1 == root2)&&&&&&&&&&&&&&& return root1;&&&&&&&&&&& if(rank[root1] & rank[root2])&&&&&&&&&&& {&&&&&&&&&&&&&&& parent[root2] = root1;&&&&&&&&&&&&&&& rank[root1] += rank[root2];&&&&&&&&&&& }&&&&&&&&&&& else&&&&&&&&&&& {&&&&&&&&&&&&&&& parent[root1] = root2;&&&&&&&&&&&&&&& rank[root2] += rank[root1];&&&&&&&&&&& }&&&&&&& }&&& }&&& int getRank(int _x)&&& {&&&&&&& return rank[_x];&&& }};char buf1[1024];
void Test(){&&& int In[30] = {0};&&& int Out[30] = {0};&&& bool visited[30] = {false};&&& UnionSet Set(28);&&&&&& scanf("%d",&n);&&& bool flag =&&& int start = 0;&&& for (int i = 0; i & ++i)&&& {&&&&&&& scanf("%s",buf1);&&&&&&& int len = strlen(buf1);&&&&&&& Set.Union(buf1[0] - a,buf1[len-1] - a);&&&&&&& In[buf1[len-1] - a]++;&&&&&&& Out[buf1[0] - a]++;&&&&&&& visited[buf1[0] - a] =&&&&&&& visited[buf1[len-1] - a] =&&&&&&& if (!flag)&&&&&&& {&&&&&&&&&&& start = buf1[0] -&&&&&&&&&&& flag =&&&&&&& }&&& }&&& &&& for (int i = 0; i & 26; ++i)&&& {&&&&&&& if (i != start)&&&&&&& {&&&&&&&&&&& if (visited[i] && (Set.root(start) != Set.root(i)))&&&&&&&&&&& {&&&&&&&&&&&&&&& printf("The door cannot be opened.
");&&&&&&&&&&&&&&&&&&&&&&&&&& }&&&&&&& }&&& }&&& int cntIn = 0;&&& int cntOut = 0;&&& for (int i = 0; i & 26; ++i)&&& {&&&&&&& if (visited[i])&&&&&&& {&&&&&&&&&&& if (In[i] != Out[i])&&&&&&&&&&& {&&&&&&&&&&&&&&& if (In[i] - Out[i] == -1)&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&& cntIn++;&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&& else if (In[i] - Out[i] == 1)&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&& cntOut++;&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&& else&&&&&&&&&&&&&nbs
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。欧拉路与欧拉回路的判断 poj -IT行业第一站
欧拉路与欧拉回路的判断 poj 1386
欧拉路与欧拉回路的判断 poj 1386
标题：欧拉路与欧拉回路的判断 poj 1386
点击打开链接
#include &iostream& #include &cstring& #include &string& #define N 100005 #define M 26 bool a[N]; int t,n,in[N],out[N],f[N],r[N]; void init() {
for(int i=0 ; i&=M ; i++)
f[i]=i,r[i]=0; } int find(int k){
return f[k]=k!=f[k]?find(f[k]):f[k]; } void union_set(int x , int y) {
int x1=find(x);
int y1=find(y);
if(x1!=y1)
if(r[x1]&r[y1]) f[x1]=y1;
else if(r[x1]&r[y1]) f[y1]=x1;
else r[y1]++,f[x1]=y1;
} } int main () {
//freopen(&1.txt&,&r&,stdin);
int i,j,k,s,e;
for(cin&&t,k=0 ; k&t; k++)
memset(a , 0 , sizeof(a));
memset(in , 0 , sizeof(in));
memset(out ,0 ,sizeof(out));
for(cin&&n,i=0 ; i& i++)
s=sh[0]-'a';
e=sh[sh.size()-1]-'a';
a[s]=1 , a[e]=1;
in[e]++ , out[s]++;
union_set(s,e);
int nt=find(e),f=0;
for(i=0 ; i&=M && f==0 ; i++ )
if(a[i] && find(i)!=nt) f=1;
for(q=p=i=0 ; i&=M && f==0; i++)
if(a[i]&&in[i]!=out[i])
if(in[i]-1==out[i]) q++;
else if(in[i]==out[i]-1) p++;
if(i&=M) f=1;
if(f!=1 &&((q+p)==0 || (p==1 && q==1)))
cout&&&Ordering is possible.&&&
else cout&&&The door cannot be opened.&&&
return 0; }
此题说白了就是一入门级别的题，只要判断出图是否连通，然后再判断是否有欧拉路 或者 欧拉回路：
无向图： 欧拉路：经过所有的边，且只存在两个奇度顶点；
& & & & & & & & &欧拉回路：经过所有的边并且是回路，全是偶度顶点。
延伸阅读：
热门搜索：POJ1386+欧拉回路_-IT行业第一站
POJ1386+欧拉回路
POJ1386+欧拉回路
标题：POJ1386+欧拉回路
1 #include&cstdio&
2 #include&vector&
3 #include&iostream&
4 #include&cstdlib&
5 #include&cstring&
6 using namespace
7 int in[30],out[30],vis[30];
10 vector&int& edge[27];
12 void dfs(int s){
for(int i=0;i&edge[s].size();i++)
if(vis[edge[s][i]]==0)
dfs(edge[s][i]);
20 bool euler(int s){
memset(vis,0,sizeof(vis));
for(i=0;i&26;i++){
if(vis[i]==0&&edge[i].size()!=0)
return false;
return true;
31 int main(){
int t,n,i,j,
char str[1010];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(i=0;i&26;i++)
edge[i].clear();
while(n--){
len=strlen(str);
out[str[0]-'a']++;
in[str[len]-'a']++;
edge[str[0]-'a'].push_back(str[len]-'a');
edge[str[len]-'a'].push_back(str[0]-'a');
//search the eulerian path
if(euler(str[0]-'a')==false){
cout&&"The door cannot be opened."&&
int f1=0,f2=0;
for(i=0;i&26;i++){
if(in[i]!=out[i]){
if(in[i]&out[i]){
if(out[i]-in[i]==1&&f1==0)
if(out[i]&in[i]){
if(in[i]-out[i]==1&&f2==0)
cout&&"Ordering is possible."&&
cout&&"The door cannot be opened."&&
延伸阅读：
热门搜索：POJ 1386 Play on Words（欧拉路径） - CSDN博客
题目大意：
首先输入T，表示测试数据的个数。之后是N,表示单词的个数。输入N个单词，如果这些单词能够首尾相连（下一个单词的首字母和上一个单词的最后一个字母相等，第一个单词和最后一个单词不要求能够首尾也相连），那么输出Ordering is possible.，否则输出The door cannot be opened.。
解题思路：
在调试这道题的时候真正体现了一个程序员的悲哀，调完提交，错了，为什么？修改，提交，错了，为什么？修改，提交，又错了，为什么？再改，提交，过了，恩！为什么？
牢骚不多说，现在来分析一下这道题：
这就是一个欧拉路径或者欧拉回路问题，首先需要根据单词构造有向图，这儿只需关注一个单词的第一个字母和最后一个字母就可以了。假设用m[30][30]来表示有向图的邻接矩阵，对于一个word而言，m[word[0]][word[strlen(word)]-1]=1,判断这个有向图能不能构成欧拉路径，首先是这个有向图必须是连通的（判断图连通的时候要把图转化为无向图来判断）。然后才能判断是否存在欧拉回路。
判断欧拉回路的方法：
对于有向图：
1、有向图是连通图；
2、每个点的出度和入度相等。
对于无向图：
1、无向图是连通图；
2、每个点的度是偶数；
判断欧拉路径的方法：
对于有向图：
1、有向图是连通图；
2、有0个或者两个顶点的出度和入读不相等（出度和入度的差值为1，且一个顶点的出度大于入度，另一个顶点的入度大于出度），其他顶点的出度和入度相等。
对于无向图：
1、无向图是连通图；
2、有0个或者两个顶点的度数为奇数，其他顶点的度数为偶数。
我在做这道题的时候WA了很多次，很大的原因是在判断连通图上，网上很多题解使用并查集来判断的，因为我没学过并查集，所以就用深搜来判断了：
正确的判断连通图的函数：
int check(int m[30][30]){
//判断图是否是连通图，返回0表示不是连通图
int i = 0;
for(i=0; i&26; i++){
if(out[i])
memset(vis,0,sizeof(vis));
int res = 0;
for(int i=0; i&26; i++){
if(!vis[i] && out[i]){
if(res & 1) return 0;
贴出之前出现错误函数代码：
int check(int m[30][30]){
int i = 0;
for(i=0; i&26; i++){
if(out[i])
memset(vis,0,sizeof(vis));
for(i=0; i&26; i++){
if(vis[i]==0 && out[i]){
完整的代码：
#include&cstdio&
#include&cstring&
int out[30],in[30];
//出度，入度
int sum[30];
//顶点的出度和入度之和
int vis[30];
int m[30][30];
//邻接矩阵
void dfs(int v){
vis[v] = 1;
for(int i=0; i&26; i++){
if(m[v][i] && !vis[i]) dfs(i);
int check(int m[30][30]){
//判断图是否是连通图，返回0表示不是连通图
int i = 0;
for(i=0; i&26; i++){
if(out[i])
memset(vis,0,sizeof(vis));
int res = 0;
for(int i=0; i&26; i++){
if(!vis[i] && out[i]){
if(res & 1) return 0;
int main(){
char str[1005];
scanf(&%d&, &t);
while(t--){
scanf(&%d&, &n);
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
memset(m,0,sizeof(m));
for(int i=0; i&n; i++){
scanf(&%s&, str);
int len = strlen(str);
out[str[0] - 'a']++;
in[str[len-1] - 'a']--;
m[str[0] - 'a'][str[len - 1] - 'a'] = 1;
m[str[len - 1] - 'a'][str[0] - 'a'] = 1;
printf(&Ordering is possible.\n&);
for(int i=0; i&26; i++){
sum[i] = out[i] + in[i];
if(!check(m)){
printf(&The door cannot be opened.\n&);
int ans=0;
int flag=0;
int flag1=0, flag2=0;
for(int i=0; i&26; i++){
if(sum[i] & -1 || sum[i] &1){
if(sum[i] == 1){
if(sum[i] == -1){
//printf(&%d\n&,flag);
printf(&The door cannot be opened.\n&);
else if((flag1==0 || flag1==1) && flag1 == flag2){
printf(&Ordering is possible.\n&);
printf(&The door cannot be opened.\n&);