|
|
#include <bits/stdc++.h>
|
|
|
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;
|
|
|
} |
