P1127 词链题目描述如果单词X XX的末字母与单词Y YY的首字母相同则X XX与Y YY可以相连成X . Y X.YX.Y。注意X XX、Y YY之间是英文的句号.。例如单词dog与单词gopher则dog与gopher可以相连成dog.gopher。另外还有一些例子dog.gophergopher.ratrat.tigeraloha.alohaarachnid.dog连接成的词可以与其他单词相连组成更长的词链例如aloha.arachnid.dog.gopher.rat.tiger注意到.两边的字母一定是相同的。现在给你一些单词请你找到字典序最小的词链使得每个单词在词链中出现且仅出现一次。注意相同的单词若出现了k kk次就需要输出k kk次。输入格式第一行是一个正整数n nn1 ≤ n ≤ 1000 1 \le n \le 10001≤n≤1000代表单词数量。接下来共有n nn行每行是一个由1 11到20 2020个小写字母组成的单词。输出格式只有一行表示组成字典序最小的词链若不存在则只输出三个星号***。输入输出样例 #1输入 #16 aloha arachnid dog gopher rat tiger输出 #1aloha.arachnid.dog.gopher.rat.tiger说明/提示对于40 % 40\%40%的数据有n ≤ 10 n \leq 10n≤10对于100 % 100\%100%的数据有n ≤ 1000 n \leq 1000n≤1000。解析/* * 思路构建: * 1.如果把输入的单词看作是一条边, 每条边利用一次, 这恰好就是一条欧拉路径 * 2.然后问题现在就落在如何建图上, 假设一个单词组成是 a***b, 那其就可以连以b开头的所有单词(边), 其就可以被所有以a结尾的单词连 * 所以以单个字母作为索引映射单词是一个可行的方案, 这样根据单词首尾字母就完美的建好了一张图, 以单个字母标记一个结点来计算出度入度 * 3.接下来就得考虑访问顺序问题, 由于是按照字典序排列, 所以索引指向的单词得按照字典序排列 * 4.然后判断这张图是否存在欧拉路径, 不存在直接输出*** * 5.如果存在就按照hierholzer算法建立欧拉路径即可 * */#includeiostream#includevector#includemap#includestring#includealgorithm#includeunordered_map#includeunordered_set#includestackusingnamespacestd;intn;string word;mapchar,vectorstringgraph;unordered_mapchar,intindegree,outdegree,start;// 标记从第几个单词开始访问chars0,t0;// 开始结点intcnt;// 统计特殊结点个数stackstringans;unordered_setcharallchars;// 记录所有出现过的字母, 以便于判断出入度是否合适voidhierholzer(charstartNode){while(start[startNode]graph[startNode].size()){stringedgegraph[startNode][start[startNode]];start[startNode];hierholzer(edge.back());ans.push(edge);// 回溯时将之前所走过的边都记录下来, 压入栈中}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;// 建图for(inti0;in;i){cinword;graph[word.front()].push_back(word);outdegree[word.front()];indegree[word.back()];allchars.insert(word.front());allchars.insert(word.back());}// 字典序升序排列for(autoe:graph){sort(e.second.begin(),e.second.end());}// 判断是否存在欧拉路径/* * 判断方法: * 如果一个有向图存在欧拉路径, 那么出了两条特殊结点意外, 其余结点出度入度都相等 * 两个特殊结点要么出入度也相等, 构成欧拉回路 * 要么一个出度边多一条, 一个入度边多一条 */for(constautoe:allchars){charnodee;if(indegree[node]!outdegree[node]){cnt;// 出度不等于入度if(!soutdegree[node]-indegree[node]1){snode;}elseif(!tindegree[node]-outdegree[node]1){tnode;}}if(cnt2)break;}if(cnt0||(cnt2st)){// 存在欧拉路径hierholzer(s?s:(graph.begin()-first));if(ans.size()n){// 这里出了考虑入度出度, 还得考虑连通性wordans.top();ans.pop();while(!ans.empty()){word.ans.top();ans.pop();}coutword\n;return0;}}cout***\n;return0;}