Catenyms

【题目描述】

现给定一组单词，如果存在某两个单词，一个单词的前缀和另一个单词的后缀相同，则认为这两个单词可以相连，例如“abce”与“efdg”可以相连，询问这组单词能否排成一排，如果可以，则输出字典序最小的排列方式。

【输入描述】

输入多组数据，对于每组数据：

第一行输入一个正整数N(3 <= N <= 1000)，表示此组单词的数目；

接下来N行，每行输入一个单词，每个单词的长度不超过20。

【输出描述】

对于每组输入数据，输出一行，表示排列方式，每两个单词之间用一个“.”隔开，如果不存在合法的排列方式，则输出“***”。

【输入样例】

2

6

aloha

arachnid

dog

gopher

rat

tiger

3

oak

maple

elm

【输出样例】

aloha.arachnid.dog.gopher.rat.tiger

***

源代码：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct Node
{
    int To,Next,Number;
    bool Flag;
}Edge[2001];
int T,n,Num,Sum,In[30],Out[30],Head[30],Ans[1001];
string S[1001];
void Add(int t1,int t2,int Number) //边表。
{
    Edge[++Num].To=t2;
    Edge[Num].Next=Head[t1];
    Edge[Num].Number=Number; //所属单词编号。
    Edge[Num].Flag=false;
    Head[t1]=Num;
}
void DFS(int T) //深搜。
{
    for (int a=Head[T];a;a=Edge[a].Next) //注意顺序，值得学习，倒序遍历，故字典序最小。
      if (!Edge[a].Flag)
      {
        Edge[a].Flag=true;
        DFS(Edge[a].To);
        Ans[Sum++]=Edge[a].Number; //记录。
      }
}
int main()
{
    cin>>T;
    while (T--)
    {
        cin>>n;
        for (int a=0;a<n;a++)
          cin>>S[a];
        sort(S,S+n); //按照字典序排序。
        Num=Sum=0;
        memset(In,0,sizeof(In));
        memset(Out,0,sizeof(Out));
        memset(Head,0,sizeof(Head));
        int Start=26;
        for (int a=n-1;a>=0;a--) //字典序大的先加入。
        {
            int t1=S[a][0]-'a'; //开头。
            int t2=S[a][S[a].length()-1]-'a'; //结尾。
            Add(t1,t2,a); //在首位之间建立一条有向边。
            Out[t1]++; //出度。
            In[t2]++; //入度。
            Start=min(Start,min(t1,t2)); //字典序最小的字母。
        }
        int T1(0),T2(0);
        for (int a=0;a<26;a++)
          if (Out[a]-In[a]==1) //只能最先出。
          {
            T1++;
            Start=a; //按照欧拉回路，如果有一个出度比入度大1的点，就从这个点出发，否则从字典序最小的点出发。
          }
          else
            if (Out[a]-In[a]==-1) //只能最后进。
              T2++;
            else
              if (Out[a]-In[a]) //怎么着都不合法了。
                T1=2;
        if (!((!T1&&!T2)||(T1==1&&T2==1))) //若不为欧拉图或半欧拉图，则退出。
        {
            cout<<"***"<<endl;
            continue;
        }
        DFS(Start);
        if (Sum!=n) //判断是否连通。
        {
            cout<<"***"<<endl;
            continue;
        }
        for (int a=Sum-1;a>=0;a--) //输出。
        {
            cout<<S[Ans[a]];
            if (a)
              cout<<".";
            else
              cout<<endl;
        }
    }
    return 0;
}

/*
    解题思路：
        其实把首尾两个字母作为节点建图，跑欧拉回路就可以了，中间的字母只是用来字典序排序的，并没有用到。
*/