#include #include #include #include #include #include #include #include using namespace std; const int N = 30; int g[N][N], din[N], dout[N]; bool st[N]; // 判断哪些字母输入了并用于连通性的判断 int n; int start; // 传入的节点 // 字符串 const int M = 1e5 + 10; char s[M]; // 连通性判断 void dfs(int u) { st[u] = 0; // 遍历到的,就标识为0,这样处理后,如果还存在未标识为0的点,就表示它是孤立点 for (int i = 0; i < 26; i++) // g[u][i]:u->i是不是有边 // st[i]:目标点是不是录入过,但没有标识过0 if (g[u][i] && st[i]) dfs(i); // 深搜 } int check() { int num1 = 0, num2 = 0; // 记录起点和终点的个数 // 利用dfs对st[i]=1的点进行标识为0,如果下面检查到还存在st[i]==1的点,说明点i不连通,也就是没有半欧拉图 dfs(start); for (int i = 0; i <= 26; i++) { if (st[i]) return 0; // 基图不连通的是不可能存在欧拉路径的 // 基图在判断完连通性后,退出历史舞台 // 下面开始的逻辑将全是有向图的逻辑 if (abs(din[i] - dout[i]) > 1) return 0; // ① 如果有点的入度和出度差大于1,不可能是半欧拉图 if (din[i] == dout[i] + 1) num1++; // ② 如果某个点的入度等于出度+1,则为终点 if (dout[i] == din[i] + 1) num2++; // ③ 如果某个点的出度等于入度+1,为起点 } // 有向图是不是半欧拉图(一笔画图),需满足: // ①:基图是不是连通 // ②:如果所有点的入度等于出度,那么此图是半欧拉图 // ③:如果存在某些点的入度与出度不一致,那么必须是一个入度比出度大1,另一个入度比出度小1,其它情况一票否决 return ((num1 == 1 && num2 == 1) || (num1 == 0 && num2 == 0)); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); memset(st, 0, sizeof st); // 是否遍历过 memset(g, 0, sizeof g); // 邻接矩阵存图 memset(din, 0, sizeof din); // 入度 memset(dout, 0, sizeof dout); // 出度 while (n--) { scanf("%s", s); int l = s[0] - 'a'; // 映射a:0,z:25 int r = s[strlen(s) - 1] - 'a'; g[l][r]++, g[r][l]++; // 因为半欧拉图就是一笔画图,是不是一笔画,需要先判断连通,而判连通需要基图,也就是对应的无向图,所以要创建无向图 din[l]++, dout[r]++; // 记录入度和出度 st[l] = st[r] = 1; // 标识已出现过  start = l; // 随意记录一个起点,以此起点开始进行dfs看看是不是图连通 } if (check()) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }