【POJ - 2337】Catenyms（欧拉图相关，欧拉通路输出路径，tricks）

题干：

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms: 

dog.gophergopher.ratrat.tigeraloha.alohaarachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example, 

aloha.aloha.arachnid.dog.gopher.rat.tiger 

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

Input

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

Output

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

Sample Input

2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger ***

题目大意：

  给n个字符串，让你串成一个串，要求输出顺序，如果多解要求字典序最小

解题报告：

   不用并查集判连通，用dfs判连通就行了。注意路径记录的时候要先dfs再回溯记录，因为可能有这种情况。

所以你需要再倒回来路径的时候记录路径，因为首先欧拉通路他只有一个终点（再也走不动的地方），你最后走不动了回溯的时候着一定是倒着回溯的，最后倒着输出就行了。

再就是注意搜索的起点：

（1）如果发现所有节点的出度与入度都相等，那么有向图中存在欧拉回路，当然也一定存在欧拉通路了。这时以任一节点开始深搜一条路径即可。（因为字典序要求最小我们就从出现的字符集中最小的那个字母开始搜）
（2）如果发现存在 out[i] - in[i] == 1 的节点，那么欧拉通路是以out[i] - in[i] == 1的那个 i 为始点的，以 in[i] - out[i] == 1 的那个 i 为终点。这时我们要以这个out[i] - in[i] == 1 的节点为起点开始深搜。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<string,int> PSI; const int MAX = 1000 + 5; string s[MAX]; int n; string ans[MAX]; int len[MAX],in[MAX],out[MAX],tot; bool vis[MAX]; vector<PSI> vv[129]; void dfs(char st) {int up = vv[st].size();for(int i = 0; i<up; i++) {PSI cur = vv[st][i];if(vis[cur.S]) continue;vis[cur.S] = 1; dfs(cur.F[len[cur.S]-1]); ans[++tot] = cur.F;} } int main() {int t;cin>>t;while(t--) {tot=0;scanf("%d",&n);for(int i = 1; i<=127; i++) in[i]=out[i]=0,vv[i].clear();for(int i = 1; i<=n; i++) {vis[i] = 0;cin>>s[i];len[i] = s[i].length();}char minn = 'z';for(int i = 1; i<=n; i++) { char st = s[i][0];char ed = s[i][len[i]-1];vv[st].pb(pm(s[i],i));in[ed]++;out[st]++;minn = min(minn,ed);minn = min(minn,st);}int flag = 1,ru=0,chu=0;for(int i = 'a'; i<='z'; i++) {sort(vv[i].begin(),vv[i].end());if(!in[i] && !out[i]) continue;if(in[i] == out[i]) continue;else if(in[i] - out[i] == 1) ru++;else if(out[i] - in[i] == 1) chu++,minn=i;else {flag = 0;break;}}if(flag == 0 || ru>1 || chu>1 || ru!=chu) puts("***");else {dfs(minn);if(tot != n) puts("***");else {for(int i = n; i>=1; i--) {if(i != n) printf(".");cout << ans[i];}puts("");}}} return 0 ; }

总结：提问，如果要求输出欧拉回路的路径咋办？答：在起点那里稍微判断一下就行了。或者最后直接输出起点。因为既然是欧拉回路的话可以以任何一个点为起点，所以你钦点的起点最后一定可以绕回来，所以最后输出答案的时候先输出一遍起点就可以。或者在dfs的时候稍微记录一下起点。

总结

以上是生活随笔为你收集整理的【POJ - 2337】Catenyms（欧拉图相关，欧拉通路输出路径，tricks）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。