单词拼接
时间限制：3000 ms | 内存限制：65535 KB
难度：5
- 描述
-
给你一些单词，请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
aloha
dog
arachnid
gopher
tiger
rat
可以拼接成：aloha.arachnid.dog.gopher.rat.tiger
- 输入
- 第一行是一个整数N(0<N<20)，表示测试数据的组数
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词，随后的M行，每行是一个长度不超过30的单词,单词全部由小写字母组成。 - 输出
- 如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".")
如果不存在拼接方案，则输出
*** - 样例输入
-
2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm
- 样例输出
-
aloha.arachnid.dog.gopher.rat.tiger ***
以字母为节点的有向图的欧拉路径，有向图的欧拉路径的充要条件是所有节点的入度等于出度，或者有一个节点的入度比出度小1，同时有一个节点的入度比出度大1。当然首先这个图得是连通的，后面会通过DFS来判断。
首先通过入度出度的条件判断能否形成欧拉路径。
若能形成，则让入度比出度小1的节点作为起始点（若没有这样的节点，就按字典顺序选第1个出现的字母作为起始点），进行dfs，找到满足条件的路径，若dfs找不到，那说明该图还是连通图
001.#include
<iostream>002.#include
<string>003.#include
<algorithm>004.#include
<vector>005.#include
<string.h>006.using namespace std;007.#define
maxM 1000008.vector<string>
words;009.int vis[maxM],M,degree_in[26],degree_out[26];010. 011.//待处理的字符串的索引，处理第x个字符串012.bool dfs(int k,int x)013.{014.if(x==M)015.return true;016.char c=words[k][words[k].size()-1];017.for(int i=0;i<M;i++)018.{019.if(vis[i]>=0||i==k)020.continue;021.if(words[i][0]==c)022.{023.vis[k]=i;024.if(dfs(i,x+1))025.return true;026.vis[k]=-1;027.}028.}029.return false;030.}031. 032.int main()033.{034.int N;035.cin>>N;036.while(N--)037.{038.cin>>M;039.words.clear();040.words.reserve(M);041.memset(degree_in,0,sizeof(degree_in));042.memset(degree_out,0,sizeof(degree_out));043.string
s;044.for(int i=0;i<M;i++)045.{046.cin>>s;047.words.push_back(s);048.degree_out[s[0]-'a']++;049.degree_in[s[s.size()-1]-'a']++;050.}051.bool flag=true;//可形成欧拉路径标志，true可形成，false不可形成052.int start=-1,dif,beg,end;053.beg=end=0;//记录入度比出度小1和入度比出度大小的点数054.for(int i=0;i<26;i++)055.{056.dif=degree_in[i]-degree_out[i];057.if(dif==0)continue;//入度等于出度058.else if(dif==-1)//入度比出度小1，可作为起始点059.{060.start=i;061.beg++;062.if(beg>=2)063.{064.flag=false;065.break;066.}067.}068.else if(dif==1)//入度比出度大1，可作为终点069.{070.end++;071.if(end>=2)072.{073.flag=false;074.break;075.}076.}077.else078.{079.flag=false;080.break;081.}082.}083.if(!flag)084.{085.cout<<"***"<<endl;086.continue;087.}088.sort(words.begin(),words.end());089.memset(vis,-1,sizeof(vis));090.if(start==-1)//没有入度比出度小1的起始点,按字典顺序选第一个字母为起始点091.{092.for(int i=0;i<26;i++)093.{094.if(degree_out[i])095.{096.start=i;097.break;098.}099.}100.}101.int k;102.for(k=0;k<M;k++)103.{104.if((words[k][0]-'a')!=start)105.continue;106.if(dfs(k,1))107.{108.int j=k;109.for(int i=0;i<M;i++)110.{111.cout<<words[j]<<((i==M-1)?'\n':'.');112.j=vis[j];113.}114.break;115.}116.}117.if(k==M)118.cout<<"***"<<endl;119.}120.return 0;121.}