题解：AcWing 1185 单词游戏

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing1185. 单词游戏 - AcWing题库【题目描述】有N NN个盘子每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序使得相邻两个盘子中前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序判断是否能达到这一要求。【输入】第一行包含整数T TT表示共有T TT组测试数据。每组数据第一行包含整数N NN表示盘子数量。接下来N NN行每行包含一个小写字母字符串表示一个盘子上的单词。一个单词可能出现多次。【输出】如果存在合法解则输出”Ordering is possible.”否则输出”The door cannot be opened.”。【输入样例】3 2 acm ibm 3 acm malform mouse 2 ok ok【输出样例】The door cannot be opened. Ordering is possible. The door cannot be opened.【核心思想】问题分析给定N NN个单词需要安排顺序使得相邻单词中前一个的末字母等于后一个的首字母。将每个单词看作一条从首字母指向尾字母的有向边问题转化为判断该有向图中是否存在欧拉路径经过每条边恰好一次的路径。这是一个欧拉路径判定问题关键在于检查图的连通性和度数条件。算法选择并查集检查所有出现过的字母是否在同一个连通分量中入度/出度统计统计每个字母作为单词开头出度和结尾入度的次数欧拉路径判定条件连通且满足特定的度数条件关键步骤建图读取每个单词首字母为a aa尾字母为b bbdout[a]首字母出度加1din[b]尾字母入度加1p[find(a)] find(b)并查集合并首尾字母检查度数条件遍历26个字母统计入度不等于出度的节点din[i] dout[i] 1入度比出度多1作为终点din[i] 1 dout[i]出度比入度多1作为起点其他情况度数差超过1不可能存在欧拉路径合法条件起点和终点都为0欧拉回路或起点和终点都为1欧拉路径检查连通性遍历所有出现过的字母检查是否属于同一个并查集集合输出结果若度数条件和连通性都满足则存在合法解时间/空间复杂度时间复杂度O ( T × ( N α ( 26 ) 26 ) ) O(T \times (N \alpha(26) 26))O(T×(Nα(26)26))其中T TT为测试组数α \alphaα为阿克曼函数的反函数可视为常数空间复杂度O ( 26 ) O(26)O(26)只需维护26个字母的度数和并查集欧拉路径的核心思想问题转化将单词接龙问题转化为有向图的欧拉路径问题每个单词是一条有向边度数守恒欧拉回路要求所有点入度等于出度欧拉路径要求恰好一个起点出度比入度多1和一个终点入度比出度多1连通性检查所有有边的节点必须在同一个连通分量中否则无法遍历所有边并查集应用高效判断连通性支持动态合并和查询适用于单词接龙、一笔画问题、路径覆盖类问题【算法标签】#欧拉路径【代码详解】#includebits/stdc.husingnamespacestd;// 常量与全局变量 constintN100005;// 最大单词数量intT;// 测试数据组数intn;// 每组数据的单词数量intdin[N];// 每个字母的入度作为末尾字母出现的次数intdout[N];// 每个字母的出度作为开头字母出现的次数intp[N];// 并查集数组boolst[N];// 标记字母是否出现过charstr[N];// 存储当前单词// 并查集查找根节点 intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}// 主函数 intmain(){cinT;while(T--){cinn;// 初始化memset(din,0,sizeof(din));memset(dout,0,sizeof(dout));memset(st,0,sizeof(st));for(inti0;i26;i)p[i]i;// 读入 n 个单词统计出入度和连通性for(inti0;in;i){cinstr;intlenstrlen(str);intastr[0]-a;// 首字母intbstr[len-1]-a;// 尾字母st[a]st[b]true;// 标记字母出现过dout[a];// 首字母出度加 1din[b];// 尾字母入度加 1p[find(a)]find(b);// 合并首尾字母所在的集合}// 检查度数条件 intstart0;// 出度比入度多 1 的节点数起点intend0;// 入度比出度多 1 的节点数终点boolsuccesstrue;for(inti0;i26;i){if(din[i]!dout[i]){if(din[i]dout[i]1)// 入度比出度多 1 → 终点end;elseif(din[i]1dout[i])// 出度比入度多 1 → 起点start;else// 度数差超过 1 → 不可能{successfalse;break;}}}// 必须有且仅有一个起点和一个终点或者没有起点和终点欧拉回路if(success!(!start!end||start1end1))successfalse;// 检查连通性 intrep-1;// 代表节点for(inti0;i26;i){if(st[i])// 如果该字母出现过{if(rep-1)repfind(i);// 记录第一个出现的字母的根节点elseif(rep!find(i))// 如果不在同一个集合中{successfalse;// 不连通break;}}}// 输出结果 if(success)coutOrdering is possible.endl;elsecoutThe door cannot be opened.endl;}return0;}【运行结果】3 2 acm ibm The door cannot be opened. 3 acm malform mouse Ordering is possible. 2 ok ok The door cannot be opened.