再学欧拉路，没搞清楚定理错了好几次
题意：给你n个单词，要求这些单词相连，要求是前面的字母的尾字母和后面单词的头字母相同，问你这n个单词能不能全部连起来，可以连成一条链或者连成一个环
另外单词只有小写字母。很容易想到，顶点集合就是26个小写字母，用1到26来表示，一个单词的首字母和尾字母就是一条有向边，注意是有向边，因为单词是不能倒回来的
其实就是问你这个图是否存在欧拉道路（一条链的情况）或者欧拉回路（环的情况），反正存在欧拉路就是成功的，否则就是失败
判断有向图是否有欧拉路
1.判断有向图的基图（即有向图转化为无向图）连通性，用简单的DFS即可。如果图都不连通，一定不存在欧拉路
2.在条件1的基础上
对于欧拉回路，要求苛刻一点，所有点的入度都要等于出度，那么就存在欧拉回路了
对于欧拉道路，要求松一点，只有一个点，出度比入度大1，这个点一定是起点； 一个点，入度比出度大1，这个点一定是终点.其余点的出度等于入度
（注意，只能大1，而且这样的点分别只能有1个,而且存在起点就一定要存在终点，存在终点就一定要存在起点）
然后就献上代码
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define N 30 int g[N][N],vis[N]; int in[N],out[N]; int n; void init() { memset(vis,0,sizeof(vis)); //判断连通性的时候要使用 memset(g,0,sizeof(g)); //构建基图 memset(in,0,sizeof(in)); //记录点的入度 memset(out,0,sizeof(out)); //记录点的出度 return ; } void input() { int u,v,len; char word[1010]; scanf("%d",&n); while(n--) { scanf("%s",word); len=strlen(word); u=word[0]-'a'+1; v=word[len-1]-'a'+1; //有向边u-->v out[u]++; in[v]++; g[u][v]=g[v][u]=1; //构建基图即有向图对应的无向图 //判断图的连通性是判断基图的连通性 //用dfs判断，也可以用并查集，这里是用dfs } return ; } void dfs(int i) { int j; for(j=1; j<=26; j++) if(g[i][j] && !vis[j]) //基图中有无向边(i,j)并且j点还没有被访问过 { vis[j]=1; dfs(j); } return ; } int DFS() { int i,count; for(count=0,i=1; i<=26; i++) if(in[i] || out[i]) //在输入中是有这个点的 if(!vis[i]) //而且这个点还没有访问过 { vis[i]=1; count++; dfs(i); } if(count>1) //基图不止一个连通分量，也就是不连通的 return 0; else return 1; } int Euler() { int i; int n1,n2; //n1记录出度把入度大1的点的个数，n2记录入度比出度大1的点的个数 n1=n2=0; for(i=1; i<=26; i++) { if(out[i]-in[i]==1) //出度比入度大1 { n1++; if(n1>1) break; //最多允许一个点的出度比入度大1，如果超过1个就不是欧拉路 } else if(in[i]-out[i]==1) //入度比出度大1 { n2++; if(n2>1) break; //最多允许一个点的入度比出度大1，如果超过1个就不是欧拉路 } else if( abs(in[i]-out[i])>1 ) //某个点的入度和出度的差值大于1，那不是欧拉路 break; } if(i<=26) //没有完整扫描完整个点集说明中途跳出，不满足欧拉路的要求 return 0; else return 1; } int main() { int T; scanf("%d",&T); while(T--) { init(); //初始化 input(); //输入 if(!DFS()) { //printf("图不连通\n"); printf("The door cannot be opened.\n"); } else //图是连通的，只要扫描一次所有的点，判断它们的度即可 { if(!Euler()) { //printf("图连通但是点的度不符合欧拉图的条件\n"); printf("The door cannot be opened.\n"); } else printf("Ordering is possible.\n"); } } return 0; }