解题思路

题意分析

本题的核心是在给定的单词字典中寻找一个复合catenym。catenym是一种特殊的单词对形式，要求第一个单词的最后一个字母和第二个单词的第一个字母相同，复合catenym则是由三个或更多单词组成的序列，且每对相邻单词都构成catenym，并且要恰好包含字典中的每个单词一次。输入包含测试用例数量$t$，每个测试用例首先输入单词数量$n$（$3\leq n\leq1000$），然后是$n$个不同的小写单词，每个单词长度在$1$到$20$个小写字母之间。输出要求是对于每个测试用例，输出字典序最小的满足条件的复合catenym，如果不存在这样的解，则输出“***”。

解题思路

1. 数据结构与初始化：
   • 定义结构体Edge来表示图的边，包含目标节点to、下一条边的索引next、边对应的单词索引index以及边是否被访问的标志flag。
   • 使用数组head存储每个节点的第一条边的索引，tot用于记录边的总数，初始化为$0$，并将head数组初始化为$-1$。
   • 定义数组str存储输入的单词，in数组记录每个节点（字母）的入度，out数组记录每个节点的出度。
2. 构建图与入度出度统计：
   • 对输入的单词按字典序进行排序，这样可以保证后续找到的解是字典序最小的。
   • 遍历单词列表，对于每个单词，将其首字母和尾字母作为图的节点，添加一条从首字母节点到尾字母节点的边，并记录边对应的单词索引。同时更新节点的入度和出度。
   • 记录所有节点中最小的节点编号作为起始节点start，同时也会根据入度和出度的情况调整start。
3. 检查欧拉路径存在性：
   • 遍历所有节点，统计出度比入度大$1$的节点数量cc1，出度比入度小$1$的节点数量cc2。
   • 根据欧拉路径的性质，若要存在欧拉路径，要么所有节点入度等于出度（cc1 == 0 && cc2 == 0），要么有且仅有一个节点出度比入度大$1$，一个节点出度比入度小$1$（cc1 == 1 && cc2 == 1）。若不满足这些条件，则不存在满足要求的复合catenym，输出“***”。
4. 深度优先搜索（DFS）寻找欧拉路径：
   • 如果存在欧拉路径，从确定的起始节点start开始进行深度优先搜索。
   • 在搜索过程中，标记已访问的边，当访问完所有边后，将边对应的单词索引记录在ans数组中。
   • 如果搜索结束后，记录的边的数量cnt不等于单词数量$n$，说明图不连通，不存在满足要求的复合catenym，输出“***”。
5. 输出结果：
   • 如果找到了满足条件的复合catenym，逆序遍历ans数组，按照单词索引输出对应的单词，并在单词之间添加句点分隔，最后输出换行符。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
using namespace std;
struct Edge
{
  int to,next;
  int index;
  bool flag;
}edge[2010];
int head[30],tot;
void init()
{
  tot = 0;
  memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int index)
{
  edge[tot].to = v;
  edge[tot].next = head[u];
  edge[tot].index = index;
  edge[tot].flag = false;
  head[u] = tot++;
}
string str[1010];
int in[30],out[30];
int cnt;
int ans[1010];
void dfs(int u)
{
  for(int i = head[u] ;i != -1;i = edge[i].next)
      if(!edge[i].flag)
      {
          edge[i].flag = true;
          dfs(edge[i].to);
          ans[cnt++] = edge[i].index;
      }
}
int main(){
  int T,n;
  scanf("%d",&T);
  while(T--){
      scanf("%d",&n);
      for(int i = 0;i < n;i++)
          cin>>str[i];
      sort(str,str+n);//要输出字典序最小的解，先按照字典序排序
      init();
      memset(in,0,sizeof(in));
      memset(out,0,sizeof(out));
      int start = 100;
      for(int i = n-1;i >= 0;i--)//字典序大的先加入
      {
          int u = str[i][0] - 'a';
          int v = str[i][str[i].length() - 1] - 'a';
          addedge(u,v,i);
          out[u]++;
          in[v]++;
          start = min(start,min(u,v));
      }
      int cc1 = 0, cc2 = 0;
      for(int i = 0;i < 26;i++){
          if(out[i] - in[i] == 1){
              cc1++;
              start = i;//如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发
          }
          else if(out[i] - in[i] == -1)
              cc2++;
          else if(out[i] - in[i] != 0)
              cc1 = 2;
      }
      if(!((cc1 == 0 && cc2 == 0)||(cc1 == 1 && cc2 == 1)))
      {
          printf("***\n");
          continue;
      }
      cnt = 0;
      dfs(start);
      if(cnt != n)//判断是否连通
      {
          printf("***\n");
          continue;
      }
      for(int i = cnt-1; i >= 0;i--)
      {
          cout<<str[ans[i]];
          if(i > 0)printf(".");
          else printf("\n");
      }
  }
  return 0;
}