欧拉道路的定义是： 除了起点和终点外，其他点的“进出” 次数应该相等。
在无向图中，除了起点和终点外，其他点的度数应该是偶数。如果一个无向图是连通的，且最多只有两个奇点，则一定存在欧拉道路。如果有两个奇点，则一定从一个出发，在另外一个终止。如果奇点不存在，则可以从任意点出发，最终一定会回到该点。
有向图欧拉道路：在‘忽略边的方向后，图必须是连通的’的前提下，最多有两个点的入度不等于出度，而且必须是其中一个点的出度比入度恰好大1（起点），另一个的入度比出度大1（终点）。 #include<stdio.h> #include<string.h> #include<math.h> int gra[26][26]; int in[26]; int out[26]; char temp[1010]; bool ok; void dfs(int u) { for(int v = 0;v < 26;v++) { if(gra[u][v]) { gra[u][v]--; dfs(v); } } } int main() { // freopen("input.txt","r",stdin); int T; scanf("%d",&T); while(T--) { int num; scanf("%d",&num); memset(gra,0,sizeof(gra)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i = 0; i < num;i++) { scanf("%s",temp); int u = temp[0]-'a'; int v = temp[strlen(temp)-1] -'a'; gra[u][v] ++; in[v]++; out[u]++; } ok = true; int bigo = 0; int smlo = 0; int start = 0; int flag =1; //没有奇点 for(int i = 0; i < 26;i++) { if(in[i]!=out[i]) { flag = 0; if(abs(in[i]-out[i])>1) ok = false; else if(in[i]-out[i]==1) { bigo++; } else if(out[i]-in[i]==1) //start { start=i; smlo++; } } } if((ok && bigo==1 && smlo==1)||flag ) { dfs(start); for(int i = 0; i < 26;i++) { for(int j=0;j < 26;j++) { if(gra[i][j]) { //图是否连通 ok = false; break; } } } if(!ok) printf("The door cannot be opened.\n"); else printf("Ordering is possible.\n"); } else { printf("The door cannot be opened.\n"); } } }
