NYIST 99 单词拼接

时间：2021-07-12 15:35:40

单词拼接
时间限制：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
***

来源
Waterloo local 2003.01.25 /POJ

上传者
张云聪

解题：判欧拉路径+连通

有向图存在欧拉路径的条件是所有点的入度等于出度，或者一个点的入度比出度大一，为终点，一点的出度比入度大一，为始点，其余的点入度等于出度。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 struct arc {

     int to,next;

     char str[];

 };

 arc e[maxn];

 int head[maxn],uf[maxn],d[maxn],tot,n,m,cnt;

 string str[maxn];

 bool vis[maxn];

 char ans[maxn][];

 bool cmp(const string &a,const string &b) {

     return a > b;

 }

 void add(int u,int v,string &s) {

     e[tot].to = v;

     e[tot].next = head[u];

     strcpy(e[tot].str,s.c_str());

     head[u] = tot++;

 }

 int Find(int x) {

     if(x != uf[x]) uf[x] = Find(uf[x]);

     return uf[x];

 }

 void dfs(int u,int id){

     for(int i = head[u]; ~i; i = e[i].next){

         if(!vis[i]){

             vis[i] = true;

             dfs(e[i].to,i);

         }

     }

     if(id > -) strcpy(ans[cnt++],e[id].str);

 }

 int main() {

     scanf("%d",&n);

     while(n--) {

         scanf("%d",&m);

         for(int i = tot = ; i < m; ++i)

             cin>>str[i];

         sort(str,str+m,cmp);

         memset(vis,false,sizeof(vis));

         memset(head,-,sizeof(head));

         for(int i = ; i < ; ++i) {

             d[i] = ;

             uf[i] = i;

         }

         for(int i = ; i < m; ++i) {

             int u = str[i][] - 'a';

             int v = str[i][str[i].length() - ] - 'a';

             d[v]--;

             d[u]++;

             add(u,v,str[i]);

             int tx = Find(u);

             int ty = Find(v);

             if(tx != ty) uf[tx] = ty;

             vis[u] = vis[v] = true;

         }

         int root = ,st = -,a = ,b = ;

         bool flag = true;

         for(int i = ; i < ; ++i){

             if(vis[i]){

                 if(i == uf[i]) root++;

                 if(root > ){

                     flag = false;

                     break;

                 }

                 if(st == -) st = i;

                 if(abs(d[i]) > ) {

                     flag = false;

                     break;

                 }

                 if(d[i] == ){

                     st = i;

                     a++;

                 }

                 if(d[i] == -) b++;

             }

         }

         if(flag &&(a == b && b ==  || a == b && b == )){

             memset(vis,false,sizeof(vis));

             cnt = ;

             dfs(st,-);

             for(int i = cnt-; i >= ; i--)

                 printf("%s%c",ans[i],i?'.':'\n');

         }else puts("***");

     }

     return ;

 }

相关文章