題干：

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個(gè)字符串，讓你串成一個(gè)串，要求輸出順序，如果多解要求字典序最小

解題報(bào)告：

? ?不用并查集判連通，用dfs判連通就行了。注意路徑記錄的時(shí)候要先dfs再回溯記錄，因?yàn)榭赡苡羞@種情況。

所以你需要再倒回來路徑的時(shí)候記錄路徑，因?yàn)槭紫葰W拉通路他只有一個(gè)終點(diǎn)（再也走不動(dòng)的地方），你最后走不動(dòng)了回溯的時(shí)候著一定是倒著回溯的，最后倒著輸出就行了。

再就是注意搜索的起點(diǎn)：

（1）如果發(fā)現(xiàn)所有節(jié)點(diǎn)的出度與入度都相等，那么有向圖中存在歐拉回路，當(dāng)然也一定存在歐拉通路了。這時(shí)以任一節(jié)點(diǎn)開始深搜一條路徑即可。（因?yàn)樽值湫蛞笞钚∥覀兙蛷某霈F(xiàn)的字符集中最小的那個(gè)字母開始搜）
（2）如果發(fā)現(xiàn)存在 out[i] - in[i] == 1 的節(jié)點(diǎn)，那么歐拉通路是以out[i] - in[i] == 1的那個(gè) i 為始點(diǎn)的，以 in[i] - out[i] == 1 的那個(gè) i 為終點(diǎn)。這時(shí)我們要以這個(gè)out[i] - in[i] == 1 的節(jié)點(diǎn)為起點(diǎn)開始深搜。

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 ; }

總結(jié)：提問，如果要求輸出歐拉回路的路徑咋辦？答：在起點(diǎn)那里稍微判斷一下就行了。或者最后直接輸出起點(diǎn)。因?yàn)榧热皇菤W拉回路的話可以以任何一個(gè)點(diǎn)為起點(diǎn)，所以你欽點(diǎn)的起點(diǎn)最后一定可以繞回來，所以最后輸出答案的時(shí)候先輸出一遍起點(diǎn)就可以。或者在dfs的時(shí)候稍微記錄一下起點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的【POJ - 2337】Catenyms（欧拉图相关，欧拉通路输出路径，tricks）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。