NYOJ99 单词拼接（欧拉+回溯）

单词拼接

时间限制：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

解析：

有向图G 为欧拉回路:
当且仅当G 的基图连通，且所有顶点的入度等于出度。
有向图G 为欧拉路:
当且仅当G 的基图连通，且只存在一个顶点u 的入度比出度大1、
只存在一个顶点v 的入度比出度小1，其它所有顶点的入度等于出度。本题还有要注意的一点就是：

单词的首字母应该看做是出度，尾字母看做是入度

代码一：----TLE
我先用并查集判断是否连通，然后再据欧拉路的条件判断是否能形成欧拉路，
最后才搜索字典序最小，超时也不足为奇，不过为此我也纠结了好几天，后来想了想可以不用使用并查集判断连通，可以再最后的搜索中边搜索边判断是否连通

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <iostream>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 const int M = 1005;
 10 struct word
 11 {
 12     char s[35];
 13     int start;
 14     int end;
 15 }str[M];
 16 int in_degree[26], out_degree[26]; // 分别记录入度和出度
 17 int father[26];   // 并查集中的数组
 18 bool use[26];   //记录首尾出现的字母，用并查集时即判断出现过的字母是否连通
 19 bool visit[M];  // 搜索路径时候回溯时候用的
 20 int ans[M];    // 结果序列
 21 int n, flagOfStart;
 22 /*要判断存在欧拉路径后输出字典序最小的路径，
 23 先把单词按字典序排序，然后判断是欧拉回路还是只是欧拉通路，
 24 如果是欧拉回路，直接从第0号单词开始搜，否则，找到出度比入度大1的
 25 那个单词开始搜标记为欧拉路起点的字母，flagOfStart即记录起点编号；
 26 
 27 
 28 int find_father(int i)
 29 {
 30     if(father[i] == -1)
 31         return i;
 32     else
 33         return find_father(father[i]);
 34 }
 35 
 36 void merge(int num1, int num2)
 37 {
 38     num1 = find_father(num1);
 39     num2 = find_father(num2);
 40     if(num1 != num2)
 41         father[num1] = num2;
 42 }
 43 
 44 void init()
 45 {
 46     memset(in_degree, 0, sizeof(in_degree));
 47     memset(out_degree, 0, sizeof(out_degree));
 48     memset(father, -1, sizeof(father));
 49     memset(visit, false, sizeof(visit));
 50     memset(use, false, sizeof(use));
 51     scanf("%d", &n);
 52     for(int i = 0; i < n; ++i)
 53     {
 54         scanf("%s", str[i].s);
 55         int len = strlen(str[i].s);
 56         str[i].start = str[i].s[0] - 'a';
 57         str[i].end = str[i].s[len-1] - 'a';
 58         use[str[i].start] = use[str[i].end] = true;
 59         merge(str[i].start, str[i].end);
 60         ++out_degree[str[i].start];
 61         ++in_degree[str[i].end];
 62     }
 63 }
 64 
 65 bool judge()
 66 {
 67     flagOfStart = 0;
 68     int cnt_in = 0;
 69     int cnt_out = 0;
 70     int tmp = 0;
 71     for(int i = 0; i < 26; ++i) //并查集判断是否连通
 72     {
 73         if(use[i] && father[i] == -1)
 74         {
 75             ++tmp;
 76             if(tmp > 1)    // 不连通
 77                 return false;
 78         }
 79     }
 80     for(int i = 0; i < 26; ++i)  // 判断是否能形成欧拉路或欧拉回路
 81     {
 82         if(!use[i])
 83             continue;
 84         if(abs(in_degree[i] - out_degree[i]) >= 2)
 85             return false;
 86 
 87         // 下边这点我把起点弄错了，害我调试了半天(我把出度和入度理解反了)
 88         if(in_degree[i] - out_degree[i] == 1) //入度比出度大一，若为欧拉路则为唯一的终点
 89             ++cnt_in;
 90         else if(in_degree[i] - out_degree[i] == -1)//入度比出度小一，若为欧拉路则为唯一的起点
 91         {
 92             ++cnt_out;
 93             flagOfStart = i;   // 若是欧拉路，则i必然是起点
 94         }
 95     }
 96     if(!flagOfStart)   //  如果是欧拉回路，则找到任意第一个出现过的字母作为搜索的起点即可
 97     {
 98         for(int i = 0; i < 26; ++i)
 99             if(use[i])
100             {
101                 flagOfStart = i;
102                 break;
103             }
104     }
105     if(cnt_out == 0 && cnt_in ==0 || cnt_out == 1 && cnt_in == 1)
106         return true;
107     return false;
108 }
109 
110 bool cmp(word p, word q)
111 {
112     return strcmp(p.s, q.s) < 0;
113 }
114 
115 void DFS(int cur)  // 在进行DFS的时候已经确定了本题的答案一定存在，
116 {                   //只是找到字典序最小的那组序列即可
117     if(cur == n)
118     {
119         for(int i = 0; i < n-1; ++i)
120             printf("%s.", str[ans[i]].s);
121         printf("%s\n", str[ans[n-1]].s);
122         return;
123     }
124     for(int i = 0; i < n; ++i)
125     {
126         if(str[i].start < flagOfStart || visit[i])
127             continue;
128         if(str[i].start > flagOfStart)
129             return;
130         ans[cur] = i;
131         visit[i] = true;
132         flagOfStart = str[i].end;
133         DFS(cur+1);
134         visit[i] = false;
135     }
136 }
137 
138 int main()
139 {
140     int T;
141     scanf("%d", &T);
142     while(T--)
143     {
144         init();
145         if(!judge())
146         {
147             printf("***\n");
148             continue;
149         }
150         sort(str, str + n, cmp);
151         DFS(0);
152     }
153     return 0;
154 }

代码二： -----没用并查集，还是超时fuck。。。。。

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <iostream>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 const int M = 1005;
 10 struct word
 11 {
 12     char s[35];
 13     int start;
 14     int end;
 15 }str[M];
 16 int in_degree[26], out_degree[26];
 17 bool use[26];   
 18 bool visit[M];
 19 int ans[M];
 20 int n, flagOfStart;
 21 
 22 void init()
 23 {
 24     memset(in_degree, 0, sizeof(in_degree));
 25     memset(out_degree, 0, sizeof(out_degree));
 26     memset(visit, false, sizeof(visit));
 27     memset(use, false, sizeof(use));
 28     scanf("%d", &n);
 29     for(int i = 0; i < n; ++i)
 30     {
 31         scanf("%s", str[i].s);
 32         int len = strlen(str[i].s);
 33         str[i].start = str[i].s[0] - 'a';
 34         str[i].end = str[i].s[len-1] - 'a';
 35         use[str[i].start] = use[str[i].end] = true;
 36         ++out_degree[str[i].start];
 37         ++in_degree[str[i].end];
 38     }
 39 }
 40 
 41 bool judge()
 42 {
 43     flagOfStart = 0;
 44     int cnt_in = 0;
 45     int cnt_out = 0;
 46     int tmp = 0;
 47     for(int i = 0; i < 26; ++i)
 48     {
 49         if(!use[i])
 50             continue;
 51         if(abs(in_degree[i] - out_degree[i]) >= 2)
 52             return false;
 53         if(in_degree[i] - out_degree[i] == 1) //入度比出度大一，若为欧拉路则为唯一的终点
 54             ++cnt_in;
 55         else if(in_degree[i] - out_degree[i] == -1)//入度比出度小一，若为欧拉路则为唯一的起点
 56         {
 57             ++cnt_out;
 58             flagOfStart = i;   // 若是欧拉路，则i必然是起点
 59         }
 60     }
 61     if(!flagOfStart)   //  如果是欧拉回路，则找到任意第一个出现过的字母作为搜索的起点即可
 62     {
 63         for(int i = 0; i < 26; ++i)
 64             if(use[i])
 65             {
 66                 flagOfStart = i;
 67                 break;
 68             }
 69     }
 70     if(cnt_out == 0 && cnt_in ==0 || cnt_out == 1 && cnt_in == 1)
 71         return true;
 72     return false;
 73 }
 74 
 75 bool cmp(word p, word q)
 76 {
 77     return strcmp(p.s, q.s) < 0;
 78 }
 79 
 80 bool DFS(int cur)
 81 {                   
 82     if(cur == n)
 83     {
 84         return true;
 85     }
 86     for(int i = 0; i < n; ++i)
 87     {
 88         if(str[i].start < flagOfStart || visit[i])
 89             continue;
 90         if(str[i].start > flagOfStart)
 91             return false;
 92         ans[cur] = i;
 93         visit[i] = true;
 94         flagOfStart = str[i].end;
 95         if(DFS(cur+1))
 96             return true;
 97         visit[i] = false;
 98     }
 99     return false;
100 }
101 
102 int main()
103 {
104     int T;
105     scanf("%d", &T);
106     while(T--)
107     {
108         init();
109         if(!judge())
110         {
111             
112         }
113         sort(str, str + n, cmp);
114         if(!DFS(0))
115         {
116            printf("***\n");
117             continue; 
118         }
119         for(int i = 0; i < n-1; ++i)
120             printf("%s.", str[ans[i]].s);
121         printf("%s\n", str[ans[n-1]].s);
122     }
123     return 0;
124 }

代码三：----AC，哥桑心了

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<algorithm>
  4 using namespace std;
  5 struct node
  6 {
  7     char s[31];
  8     int first,last;
  9 };
 10 
 11 node a[1001];
 12 int degree_in[1001],degree_out[1001],m,order[1001];
 13 bool used[1001];
 14 
 15 int f()
 16 {
 17     int x1,x2,ans=0,i;
 18     x1=x2=0;
 19     for(i=0;i<26;++i)
 20     {
 21         if(abs(degree_in[i]-degree_out[i])>=2)
 22             return -1;
 23         else if(degree_in[i]-degree_out[i]==1)
 24             x1++;
 25         else if(degree_in[i]-degree_out[i]==-1)
 26         {
 27             x2++;
 28             ans=i;
 29         }
 30     }
 31         if(x1>1||x2>1) //当时三个度时，必定是 12 和21，相同的不能大于等于2，不然不能构成欧拉回路
 32             return -1;
 33         else if(x1==0)
 34         {
 35             for(i=0;i<26;++i)
 36                 if(degree_out[i])
 37                     return i; //找到一个就行
 38         }
 39         else
 40             return ans;
 41 
 42 }
 43 bool cmp(node a,node b)
 44 {
 45     return strcmp(a.s,b.s)<0;
 46 }
 47 
 48 bool dfs(int st,int cnt)
 49 {
 50     int i;
 51     if(cnt==m)
 52         return 1;
 53     for(i=0;i<m;++i)
 54     {
 55         if(a[i].first<st||used[i])
 56             continue;
 57         else if(a[i].first>st)
 58             return false;
 59         used[i]=true;
 60         order[cnt]=i;
 61         if(dfs(a[i].last,cnt+1))
 62             return 1;
 63         used[i]=false;//回溯判断是否形成欧拉路径
 64     }
 65     return false;
 66 }
 67 
 68 
 69 int main()
 70 {
 71     int N,len,i,start;
 72     scanf("%d",&N);
 73     while(N--)
 74     {
 75         memset(used,false,sizeof(used));
 76         memset(degree_out,0,sizeof(degree_out));
 77         memset(degree_in,0,sizeof(degree_in));
 78         scanf("%d",&m);
 79         for(i=0;i<m;++i)
 80         {
 81             scanf("%s",a[i].s);
 82             len = strlen(a[i].s);
 83             a[i].first =a[i].s[0]-'a';
 84             a[i].last =a[i].s[len-1]-'a';
 85             degree_out[a[i].s[0]-'a']++;
 86             degree_in[a[i].s[len-1]-'a']++;//注意这里的入肚出度
 87         }
 88         start=f();
 89         if(start ==-1)
 90         {
 91             printf("***\n");
 92             continue;
 93         }
 94         sort(a,a+m,cmp);
 95         if(!dfs(start,0))
 96         {
 97             printf("***\n");
 98             continue;
 99         }
100        printf("%s",a[order[0]].s);
101       for(i=1;i<m;i++)
102          printf(".%s",a[order[i]].s);
103       printf("\n");
104     }
105     return 0;
106 }

功不成，身已退