1528：【例 2】单词游戏

题目描述

来自 ICPC CERC 1999/2000，有改动。

有 $N$ 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。

注意：本题只要求判断是否存在合法顺序，不要求输出具体顺序。

输入格式

多组数据。第一行给出数据组数 $T$，每组数据第一行给出盘子数量 $N$，接下去 $N$ 行给出小写字母字符串，一种字符串可能出现多次。

输出格式

若存在一组合法解输出 Ordering is possible.，否则输出 The door cannot be opened.。

样例

样例输入 #1

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

样例输出 #1

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

样例解释 #1

第一组数据：

• $N=2$ 个单词：acm（首字母 a，末字母 m），ibm（首字母 i，末字母 m）。
• 前一个单词的末字母必须等于后一个单词的首字母。acm 末字母 m，ibm 首字母 i，不匹配；ibm 末字母 m，acm 首字母 a，也不匹配。无法排列，输出 The door cannot be opened.。

第二组数据：

• $N=3$ 个单词：acm（a→m），malform（m→m），mouse（m→e）。
• 可以排列为：acm（a→m），malform（m→m），mouse（m→e），满足相邻首尾字母匹配。输出 Ordering is possible.。

第三组数据：

• $N=2$ 个单词：ok（o→k），ok（o→k）。
• 第一个 ok 末字母 k，第二个 ok 首字母 o，不匹配；反过来也不匹配。无法排列，输出 The door cannot be opened.。

数据范围

• $1 \le N \le 10^5$
• $|S| \le 1000$

时空限制

• 时间限制：1000 ms
• 内存限制：32768 KB

注意：本题可以转化为有向图欧拉路径/回路问题。将 $26$ 个小写字母看作节点，每个单词看作从首字母指向末字母的一条有向边（如果首尾字母相同，则为自环）。问题转化为判断有向图是否存在欧拉路径（或回路），即是否存在一条路径经过每条边恰好一次（即所有单词恰好用一次）。判断条件：

1. 图是弱连通的（即忽略方向后连通，忽略孤立点）。
2. 每个节点的入度等于出度（欧拉回路），或者恰好有两个节点入度不等于出度，其中一个节点入度比出度多 $1$（终点），另一个节点出度比入度多 $1$（起点），其余节点入度等于出度（欧拉路径）。

注意自环不影响度数（因为入度和出度都增加 $1$）。由于单词数量 $N$ 可能很大，但字母只有 $26$ 个，所以图的规模很小。