大意略。
思路:有向图的欧拉路径。
条件:
1、连通
2、有2个奇点,其中出度比入度一个大1,起点,另一个小1,终点。
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 50; int ind[maxn], outd[maxn]; int vis[maxn]; int p[maxn]; int G[maxn][maxn]; char str[1010]; int n; void init() { memset(G, 0, sizeof(G)); memset(vis, 0, sizeof(vis)); memset(ind, 0, sizeof(ind)); memset(outd, 0, sizeof(outd)); for(int i = 0; i < 27; i++) p[i] = i; } int find(int x) { return x == p[x]? x: p[x] = find(p[x]); } void Union(int a, int b) { int x = find(a), y = find(b); if(x == y) return ; p[x] = y; } int check() { int s = 0; for(int i = 0; i < 27; i++) if(vis[i] && p[i] == i) s++; return s == 1; } void read_case() { init(); scanf("%d", &n); while(n--) { scanf("%s", str); int u = str[0]-'a', v = str[strlen(str)-1]-'a'; G[u][v] = 1; ind[v]++, outd[u]++; Union(u, v); vis[u] = vis[v] = 1; } } void solve() { int flag = 1; read_case(); if(!check()) flag = 0; int c1 = 0, c2 = 0; for(int i = 0; i < 27; i++) if(vis[i]) { if(outd[i] != ind[i]) { if(outd[i] - ind[i] == 1) c1++; else if(ind[i] - outd[i] == 1) c2++; else { flag = 0; break; } } } if(c1+c2 > 2) flag = 0; if(flag) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }