字典序最小欧拉路

首先跑一个出度减入度。

1、如果存在一个为1一个为-1，则为出度减入度为1的点是唯一合法的起点

2、如果入度减出度都为0，则任意点都是合法的起点，为了字典序最小，需要选择字典序最小的字母做起点

3、如果有多个为1或者存在出度减度数大于1的则无解

其次需要连通，可以读入边时做并查集，确定起点后，扫一遍图上的点，看看是否和起点在一个连通块里即可

做完之后就已经确定有解了，考虑首先跑一个字典序最小的合法的路。这有可能导致有些边没有被加入，例如这种情况：

图片不会加，你就考虑abcd一条线过去了，但是比如b还有个环befgb，这种如何解决呢？

只需要从后往前扫描刚跑出来的路上的点，如果还有边没加进去，就贪心地选最劣的边往里加即可。 代码使用了stack来回倒，复杂度$tnlogn$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x;
    cin>>x;
    return x;
}
int n,ru[200],fa[200],flag,now;
multiset<string>o[200];
stack<string>print,ans;
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
    if(x!=y)
        fa[x]=y;
}
void work()
{
    n=read();
    for(int i='a';i<='z';i++)
    {
        o[i].clear();
        ru[i]=0;
        fa[i]=i;
    }
    while(ans.size())
        ans.pop();
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        o[s[0]].insert(s);
        ru[s[0]]++;
        ru[s.back()]--;
        merge(get(s[0]),get(s.back()));
    }
    now=-1;
    for(int i='a';i<='z';i++)
    {
        if(ru[i]==1)
        {
            if(now==-1)
                now=i;
            else
            {
                printf("***\n");
                return ;
            }
        }
        if(ru[i]>1||ru[i]<-1)
        {
            printf("***\n");
            return ;
        }
    }
    if(now==-1)
    {
        for(int i='a';i<='z';i++)
            if(o[i].size())
            {
                now=i;
                break;
            }
    }
    for(int i='a';i<='z';i++)
        if(o[i].size()&&get(i)!=get(now))
        {
            cout<<"***\n";
            return;
        }
    while(o[now].size())
    {
        int t=now;
        string s=*o[now].begin();
        ans.push(s);
        now=s.back();
        o[t].erase(o[t].find(s));
    }
    flag=0;
    while(ans.size())
    {
        while(o[ans.top().back()].size())
        {
            now=ans.top().back();
            while(o[now].size())
            {
                int t=now;
                ans.push(*o[now].begin());
                now=(*o[now].begin()).back();
                o[t].erase(o[t].begin());
            }
        }
        print.push(ans.top());
        ans.pop();
    }
    cout<<print.top();
    print.pop();
    while(print.size())
    {
        cout<<'.'<<print.top();
        print.pop();
    }
    cout<<'\n';
}
int main()
{
    // freopen("1.in","r",stdin);
    for(int t=read();t;t--)
        work();
}
using namespace std;
typedef long long ll;
ll read()
{
    ll x;
    cin>>x;
    return x;
}
int n,ru[200],fa[200],flag,now;
multiset<string>o[200];
stack<string>print,ans;
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
    if(x!=y)
        fa[x]=y;
}
void work()
{
    n=read();
    for(int i='a';i<='z';i++)
    {
        o[i].clear();
        ru[i]=0;
        fa[i]=i;
    }
    while(ans.size())
        ans.pop();
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        o[s[0]].insert(s);
        ru[s[0]]++;
        ru[s.back()]--;
        merge(get(s[0]),get(s.back()));
    }
    now=-1;
    for(int i='a';i<='z';i++)
    {
        if(ru[i]==1)
        {
            if(now==-1)
                now=i;
            else
            {
                printf("***\n");
                return ;
            }
        }
        if(ru[i]>1||ru[i]<-1)
        {
            printf("***\n");
            return ;
        }
    }
    if(now==-1)
    {
        for(int i='a';i<='z';i++)
            if(o[i].size())
            {
                now=i;
                break;
            }
    }
    for(int i='a';i<='z';i++)
        if(o[i].size()&&get(i)!=get(now))
        {
            cout<<"***\n";
            return;
        }
    while(o[now].size())
    {
        int t=now;
        string s=*o[now].begin();
        ans.push(s);
        now=s.back();
        o[t].erase(o[t].find(s));
    }
    flag=0;
    while(ans.size())
    {
        while(o[ans.top().back()].size())
        {
            now=ans.top().back();
            while(o[now].size())
            {
                int t=now;
                ans.push(*o[now].begin());
                now=(*o[now].begin()).back();
                o[t].erase(o[t].begin());
            }
        }
        print.push(ans.top());
        ans.pop();
    }
    cout<<print.top();
    print.pop();
    while(print.size())
    {
        cout<<'.'<<print.top();
        print.pop();
    }
    cout<<'\n';
}
int main()
{
    // freopen("1.in","r",stdin);
    for(int t=read();t;t--)
        work();
}