2025年acwing1185. 单词游戏(欧拉图)「建议收藏」

编程汇总 • 2025-10-02 15:40 • 阅读 53

有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。

你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。

请你编写一个程序，判断是否能达到这一要求。

每组数据第一行包含整数 N，表示盘子数量。

接下来 N 行，每行包含一个小写字母字符串，表示一个盘子上的单词。

一个单词可能出现多次。

数据范围
1≤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 
  
    
     
     
 using namespace std; 
 const int N = 26; 
 int f[N],in[N],out[N],vis[N]; 
 int find(int x){ 
 
 return f[x] = (x == f[x] ? f[x] : find(f[x])); 
 } 
 
 int main(){ 
 
 int T; 
 scanf("%d",&T); 
 int n; 
 while(T --){ 
 
 memset(in,0,sizeof in); 
 memset(out,0,sizeof out); 
 memset(vis,0,sizeof vis); 
 for(int i = 0;i < 26;i ++)f[i] = i; 
 scanf("%d",&n); 
 char s[1010]; 
 while(n --){ 
 
 scanf("%s",s); 
 int a = s[0] - 'a',b = s[strlen(s) - 1] - 'a'; 
 in[b] ++ ,out[a] ++; 
 f[find(a)] = find(b); 
 vis[a] = vis[b] = true; 
 } 
 int l = 0,h = 0; 
 bool f = true; 
 for(int i = 0;i < 26;i ++){ 
 
 if(in[i] != out[i]){ 
 
 if(in[i] == out[i] + 1)l ++; 
 else if(in[i] == out[i] - 1)h ++; 
 else f = false; 
 } 
 } 
 if(f && ((l != 1 || h != 1) && !(l == 0 && h == 0)))f = false; 
 int p = -1; 
 for(int i = 0;i < 26;i ++){ 
 
 if(vis[i]){ 
 
 if(p == -1)p = find(i); 
 else if(find(i) != p){ 
 
 f = false; 
 break; 
 } 
 } 
 } 
 if(!f)cout<<"The door cannot be opened."< 
                                                             else cout<<"Ordering is possible."< 
                                                             } 
 return 0; 
 }

今天的文章 2025年acwing1185. 单词游戏(欧拉图)「建议收藏」分享到此就结束了，感谢您的阅读。

2025年acwing1185. 单词游戏(欧拉图)「建议收藏」

相关推荐