#include using namespace std; const int N = 1010, M = 100010; int m; int din[N], dout[N]; int cnt; // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } // 欧拉通路+删边优化+边记数 void dfs(int u) { for (int i = h[u]; ~i; i = h[u]) { h[u] = ne[i]; dfs(e[i]); cnt++; } } int main() { char str[N]; // char数组的性能比string要强!建议使用此方法 int T; scanf("%d", &T); while (T--) { memset(h, -1, sizeof h); idx = cnt = 0; memset(din, 0, sizeof din); memset(dout, 0, sizeof dout); scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%s", str); // 配合字符数组完成字符串读入 int a = str[0] - 'a', b = str[strlen(str) - 1] - 'a'; add(a, b); // 有向图建边 din[b]++, dout[a]++; } // 枚举每个字母映射的节点0~25 int start = 0, s = 0, e = 0; // start:起点,s:起点个数,e:终点个数 for (int i = 0; i < 26; i++) if (din[i] != dout[i]) { // 如果入度与出度不相等,那么必须是一个起点,一个终点 if (din[i] == dout[i] - 1) // 入度=出度-1 ->起点 start = i, s++; // 记录起点 else if (din[i] == dout[i] + 1) // 入度=出度+1 ->终点 e++; else { // 没有欧拉通路,标识start=-1,表示检查失败 start = -1; break; } } // start==-1 : 不存在欧拉路径 // s> 1 || e>1 : 起点数量大于1,或者终点数量大于1 if (start == -1 || s > 1 || e > 1) { puts("The door cannot be opened."); continue; } // 用dfs判断是否连通,用上面的欧拉定理先把度的事处理完,再dfs,可以提速 dfs(start); // 如果枚举到的边数小于图中的边,表示没走全,说明图不连通 if (cnt < m) puts("The door cannot be opened."); else puts("Ordering is possible."); } return 0; }