POJ2337.md

欧拉路径，要求字典序最小，先把字符串按字典序排序，然后所有边代表的字符串再排序

#include<cstring>
#include<string>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;
const int MAXN = 30;
char buf[MAXN];
string str[1111];
vector<pair<int,int> > G[MAXN];
int n,ind[MAXN],outd[MAXN],vis[MAXN][1111];
stack<int> stk;
void dfs(int u){
    for(int i = 0; i < (int)G[u].size(); i++){
        if(vis[u][i]) continue;
        vis[u][i] = true;
        dfs(G[u][i].second);
        stk.push(G[u][i].first);
    }
}
void solve(){
    for(int i = 0; i < MAXN; i++) G[i].clear();
    memset(ind,0,sizeof(ind));
    memset(outd,0,sizeof(outd));
    memset(vis,0,sizeof(vis));
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%s",buf);
        str[i].assign(buf);
    }
    sort(str+1,str+1+n);
    for(int i = 1; i <= n; i++){
        int u = str[i][0] - 'a';
        int v = str[i][str[i].size()-1] - 'a';
        G[u].push_back(make_pair(i,v));
        ind[v]++; outd[u]++;
    }
    int gt = -1, lt = -1;
    for(int i = 0; i < 26; i++){
        if(fabs(ind[i]-outd[i])>1) return (void)puts("***");
        if(ind[i]>outd[i]){
            if(gt!=-1) return (void)puts("***");
            else gt = i;
        }
        if(outd[i]>ind[i]){
            if(lt!=-1) return (void)puts("***");
            else lt = i;
        }
    }
    for(int i = 0; i < 26; i++) sort(G[i].begin(),G[i].end());
    if(lt!=-1) dfs(lt);
    else{
        for(int i = 0; i < 26; i++) if(outd[i]){
            dfs(i);
            break;
        }
    }
    if(stk.size()!=n){
        puts("***");
        while(!stk.empty()) stk.pop();
        return;
    }
    while(!stk.empty()){
        printf("%s",str[stk.top()].c_str());
        stk.pop();
        if(!stk.empty()) putchar('.');
    }
    puts("");
}
int main(){
    int T;
    for(scanf("%d",&T); T; T--) solve();
    return 0;
}