POJ 2337 欧拉路

Catenyms

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11214		Accepted: 2908

Description

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.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.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
***

Source

Waterloo local 2003.01.25

　　省赛那道最小生成树的题模板套了很久一直都是错的，才感觉自己好像只是手里拿着一些自己熟悉图论的模板而已，实际上什么也不会，基础逃过不扎实。

　　大致题意：给定一些字符串，要求像成语接龙一般把所有字符串连接起来，如果存在多种情况，按字典序最小的那种输出。

　　题解：一个欧拉路的题，因为要求以字典序输出，所以得先对输入的字符串进行字典序排序排序（做到这题才知道 string 类型的可以直接排序，结果就是字典序，果然还是得多多学习）。接着 a,b,c 等字母为顶点以每个字符串为边，从首字母指向尾字母，（最开始以每个单词为顶点老是不行，在看了题解后才改过来）。建好图以后就是一个直接的欧拉回路问题了，分别先判断联通与否以及是否能够构成欧拉图，然后便是路径输出了。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int n,vis[1005],len[1005],k,in[1005],out[1005],ans[1005],cnt;
string s[1005];
struct node{
    int u,m;
};
vector<node> g[1005];
void euler(int x){
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i].u;
        if(!vis[ g[x][i].m ]){
            vis[ g[x][i].m ]=1;
            euler(v);
            cnt++;
            ans[cnt]=g[x][i].m;
        }
    }
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        int start=100;
        cin >> n;
        k=0;
        memset(vis,0,sizeof(vis));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        for(int i=1;i<=26;i++) g[i].clear();
        for(int i=1;i<=n;i++){
            cin >> s[i];
        }
        sort(s+1,s+n+1);
        for(int i=1;i<=n;i++){
            len[i]=s[i].size();
        }
        for(int i=1;i<=n;i++){
            node t;
            t.u=s[i][len[i]-1]-'a'+1; t.m=i;
            g[ s[i][0]-'a'+1 ].push_back( t );
            out[ s[i][0]-'a'+1 ]++; in[s[i][len[i]-1]-'a'+1]++;
            start=min(start,s[i][0]-'a'+1);
            start=min(start,s[i][len[i]-1]-'a'+1);
        }
        int fin=0,fout=0,end=0,flag=0;
        for(int i=1;i<=26;i++){
            if(in[i]+1==out[i]){
                start=i; fin++;
            }
            else if(in[i]==out[i]+1){
                fout++;
            }
            else if(in[i]!=out[i]) flag=1;
        }
        if(flag==1) { printf("***
"); continue; }
        else if( (fin==1&&fout==1) || (fin==0&&fout==0) ) {
            cnt=0;
            euler(start);
            if(cnt==n){
                for(int i=cnt;i>=1;i--) {
                    if(i==cnt) cout << s[ ans[i] ];
                    else cout << "." << s[ ans[i] ];
                }
                printf("
");
            }
            else { printf("***
"); continue; }
        }
        else { printf("***
"); continue; }
    }

    return 0;
}

Psong