欧拉回路和欧拉路径-----------单词游戏

Sabah ·

更新时间:2024-09-20

· 531 次阅读

有 NN 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。
你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。
请你编写一个程序，判断是否能达到这一要求。
输入格式
第一行包含整数 TT，表示共有 TT 组测试数据。
每组数据第一行包含整数 NN，表示盘子数量。
接下来 NN 行，每行包含一个小写字母字符串，表示一个盘子上的单词。
一个单词可能出现多次。
输出格式
如果存在合法解，则输出”Ordering is possible.”，否则输出”The door cannot be opened.”。
数据范围
1≤N≤1051≤N≤105,

单词长度均不超过1000
输入样例：
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

输出样例：
The door cannot be opened.
Ordering is possible.
The door cannot be opened.

#include 
#include 
#include 
#include 
using namespace std;
const int N = 30;
int n;
int din[N], dout[N];
bool st[N];
int p[N];
int find(int x){
 if (p[x] != x)     p[x] = find(p[x]);
 return  p[x];
}
int main(){
 char str[1010];
  int T;
 scanf("%d", &T);
 while(T --){
  scanf("%d", &n);
  memset(din, 0, sizeof din);
  memset(dout, 0, sizeof dout);
  memset(st, 0, sizeof st);
    for (int i = 0; i < 26; i ++)    p[i] = i;
    for (int i = 0; i < n; i ++){
   scanf("%s", str);
   int len = strlen(str);
   int a = str[0] - 'a', b = str[len - 1] - 'a';
   st[a] = st[b] = true;
            dout[a] ++, din[b] ++;
            p[find(a)] = find(b);
  }
    int start = 0, end = 0;
  bool success = true;
    for (int i = 0; i < 26; i ++)
      if (din[i] != dout[i]){
       if (din[i] == dout[i] + 1)   end ++;
       else if (din[i] + 1 == dout[i])  start ++;
       else{
        success = false;
        break;
    }
   }
        if (success && !(!start && !end || start == 1 && end == 1))
         success = false;
              int rep = -1;
     for (int i = 0; i < 26; i ++)
        if (st[i]){
         if (rep == -1)   rep = find(i);
         else       if (rep != find(i)){
           success = false;
           break;
       }
          }
                if (success)   puts("Ordering is possible.");
   else           puts("The door cannot be opened.");
 }
    return 0;
}