NYIST 99 单词拼接

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

上传者
张云聪

解题：判欧拉路径+连通

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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define pii pair<int,int>
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 1010;
 18 struct arc {
 19     int to,next;
 20     char str[30];
 21 };
 22 arc e[maxn];
 23 int head[maxn],uf[maxn],d[maxn],tot,n,m,cnt;
 24 string str[maxn];
 25 bool vis[maxn];
 26 char ans[maxn][30];
 27 bool cmp(const string &a,const string &b) {
 28     return a > b;
 29 }
 30 void add(int u,int v,string &s) {
 31     e[tot].to = v;
 32     e[tot].next = head[u];
 33     strcpy(e[tot].str,s.c_str());
 34     head[u] = tot++;
 35 }
 36 int Find(int x) {
 37     if(x != uf[x]) uf[x] = Find(uf[x]);
 38     return uf[x];
 39 }
 40 void dfs(int u,int id){
 41     for(int i = head[u]; ~i; i = e[i].next){
 42         if(!vis[i]){
 43             vis[i] = true;
 44             dfs(e[i].to,i);
 45         }
 46     }
 47     if(id > -1) strcpy(ans[cnt++],e[id].str);
 48 }
 49 int main() {
 50     scanf("%d",&n);
 51     while(n--) {
 52         scanf("%d",&m);
 53         for(int i = tot = 0; i < m; ++i)
 54             cin>>str[i];
 55         sort(str,str+m,cmp);
 56         memset(vis,false,sizeof(vis));
 57         memset(head,-1,sizeof(head));
 58         for(int i = 0; i < 26; ++i) {
 59             d[i] = 0;
 60             uf[i] = i;
 61         }
 62         for(int i = 0; i < m; ++i) {
 63             int u = str[i][0] - 'a';
 64             int v = str[i][str[i].length() - 1] - 'a';
 65             d[v]--;
 66             d[u]++;
 67             add(u,v,str[i]);
 68             int tx = Find(u);
 69             int ty = Find(v);
 70             if(tx != ty) uf[tx] = ty;
 71             vis[u] = vis[v] = true;
 72         }
 73         int root = 0,st = -1,a = 0,b = 0;
 74         bool flag = true;
 75         for(int i = 0; i < 26; ++i){
 76             if(vis[i]){
 77                 if(i == uf[i]) root++;
 78                 if(root > 1){
 79                     flag = false;
 80                     break;
 81                 }
 82                 if(st == -1) st = i;
 83                 if(abs(d[i]) > 1) {
 84                     flag = false;
 85                     break;
 86                 }
 87                 if(d[i] == 1){
 88                     st = i;
 89                     a++;
 90                 }
 91                 if(d[i] == -1) b++;
 92             }
 93         }
 94         if(flag &&(a == b && b == 1 || a == b && b == 0)){
 95             memset(vis,false,sizeof(vis));
 96             cnt = 0;
 97             dfs(st,-1);
 98             for(int i = cnt-1; i >= 0; i--)
 99                 printf("%s%c",ans[i],i?'.':'
');
100         }else puts("***");
101     }
102     return 0;
103 }

View Code