本文主要是介绍POJ 1386 Play on Words（欧拉路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
首先输入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]) break;}memset(vis,0,sizeof(vis));int res = 0;for(int i=0; i<26; i++){if(!vis[i] && out[i]){res++;dfs(i);}}if(res > 1) return 0;return 1;
}贴出之前出现错误函数代码：
int check(int m[30][30]){int i = 0;for(i=0; i<26; i++){if(out[i]) break;}memset(vis,0,sizeof(vis));dfs(i);for(i=0; i<26; i++){if(vis[i]==0 && out[i]){return 0;}}return 1;
}完整的代码：
#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);}return ;
}
int check(int m[30][30]){ //判断图是否是连通图，返回0表示不是连通图int i = 0;for(i=0; i<26; i++){if(out[i]) break;}memset(vis,0,sizeof(vis));int res = 0;for(int i=0; i<26; i++){if(!vis[i] && out[i]){res++;dfs(i);}}if(res > 1) return 0;return 1;
}
int main(){int t, n;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;}if(n==1){printf("Ordering is possible.\n");continue;}for(int i=0; i<26; i++){sum[i] = out[i] + in[i];}if(!check(m)){printf("The door cannot be opened.\n");continue;}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){flag = 1;break;}if(sum[i] == 1){flag1++;}if(sum[i] == -1){flag2++;}}//printf("%d\n",flag);if(flag){printf("The door cannot be opened.\n");}else if((flag1==0 || flag1==1) && flag1 == flag2){printf("Ordering is possible.\n");}else{printf("The door cannot be opened.\n");}}return 0;
}
这篇关于POJ 1386 Play on Words（欧拉路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
