看题目是字符串处理,但实际上是欧拉回路
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int LEN = 30;

struct HEAD
{
    int in;
    int out;
    int next;
    int last;
}head[LEN];

struct NODE
{
    int num;
    int weight;
    int used;
    int next;
    int other;
}node[LEN*500];
int next_n;

void init_m ( int n )
{

    next_n = 0;
    for ( int i=0; i<n; i++ )
    {
        head[i].in = head[i].out = 0;
        head[i].next = -1;
    }
}

void ins ( int a, int b, int weight )
{

    node[next_n].next = -1;
    node[next_n].num = b;
    node[next_n].used = 0;
    node[next_n].weight = weight;
    next_n ++;

    if ( head[a].next==-1 )
        head[a].next = next_n-1;
    else
        node[ head[a].last ].next = next_n-1;
    head[a].last = next_n-1;
    head[a].out ++;
    head[b].in ++;
}

//预处理部分
struct SEGMENT
{
    char str[LEN];
    int len;
}seg[LEN*500];
int hash[LEN];
char ch[LEN];
int next_ch;
int flag[LEN];

void init ()
{

    next_ch = 0;
    for ( int i=0; i<LEN; i++ )
        hash[i] = 0;
}

int cmp1 ( const void *a, const void *b )
{

    return strcmp ( ((SEGMENT *)a)->str, ((SEGMENT *)b)->str );
}

int cmp2 ( const void *a, const void *b )
{

    return *(char *)a-*(char *)b;
}

void ser ( int used[], int s, int n, int &f )
{

    used[s] = 1;
    f ++;
    for ( int i=head[s].next; i!=-1; i=node[i].next )
    {
        if ( !used[ node[i].num ] )
            ser ( used, node[i].num, n, f );
    }
}

int canget ( int used[], int p, int e )
{

    used[p] = 1;
    if ( p==e )
        return 1;
    for ( int i=head[p].next; i!=-1; i=node[i].next )
    {
        if ( !node[i].used&&!used[ node[i].num ] )
        {
            if ( canget ( used, node[i].num, e ) )
                return 1;
        }
    }
    return 0;
}

void print ( int p, int total, int &count )
{

    int flag = 0;
    for ( int i=head[p].next; i!=-1; i=node[i].next )
    {
        if ( !node[i].used )
        {
            flag = 1;
            node[i].used = 1;
            int used[LEN] = {0};
            if ( canget ( used, node[i].num, p ) )
            {
                printf ( "%s", seg[ node[i].weight ].str );
                count ++;
                if ( count!=total )
                    printf ( "." );
                print ( node[i].num, total, count );
            }
            else
                node[i].used = 0;
        }
    }
    if ( flag )
    {
        for ( int i=head[p].next; i!=-1; i=node[i].next )
        {
            if ( !node[i].used )
            {
                node[i].used = 1;
                printf ( "%s", seg[ node[i].weight ].str );
                count ++;
                if ( count!=total )
                    printf ( "." );
                print ( node[i].num, total, count );
            }
        }
    }
}

void work ( int n )
{

    qsort ( ch, next_ch, sizeof ( char ), cmp2 );
    for ( int i=0; i<next_ch; i++ )
        flag[ ch[i]-'a' ] = i;

    qsort ( seg, n, sizeof ( SEGMENT ), cmp1 );
    init_m ( next_ch );
    for ( int i=0; i<n; i++ )
    {
        int a = flag[ seg[i].str[0]-'a' ];
        int b = flag[ seg[i].str[ seg[i].len-1 ]-'a' ];
        ins ( a, b, i );
    }

    //检查连通性
    int f = 0;
    for ( int i=0; i<next_ch; i++ )
    {
        int used[LEN] = {0};
        f = 0;
        ser ( used, i, n, f );
        if ( f==next_ch )
            break;
    }
    if ( f<next_ch )
    {
        printf ( "***\n" );
        return;
    }

    //检查出入度
    int ans1 = 0;
    int ans2 = 0;
    int no1, no2;
    for ( int i=0; i<next_ch; i++ )
    {
        if ( head[i].in-head[i].out==1 )
        {
            ans1 ++;
            no1 = i;
        }
        else if ( head[i].in-head[i].out==-1 )
        {
            ans2 ++;
            no2 = i;
        }
        else if ( abs (head[i].in-head[i].out)>1 )
        {
            ans1 = ans2 = LEN;
        }
    }
    if ( !((ans1==0&&ans2==0)||(ans1==1&&ans2==1)) )
    {
        printf ( "***\n" );
        return;
    }

    //查找路径
    int count = 0;
    if ( ans1==0&&ans2==0 )
        print ( 0, n, count );
    else
        print ( no2, n, count );
    printf ( "\n" );

}

int main ()
{

    int t;
    scanf ( "%d", &t );
    while ( t-- )
    {
        int n;
        scanf ( "%d", &n );
        init ();
        for ( int i=0; i<n; i++ )
        {
            scanf ( "%s", seg[i].str );
            seg[i].len = strlen ( seg[i].str );
            if ( !hash[ seg[i].str[0]-'a' ] )
            {
                ch[next_ch++] = seg[i].str[0];
                hash[ seg[i].str[0]-'a' ] = 1;
            }
            if ( !hash[ seg[i].str[seg[i].len-1]-'a' ] )
            {
                ch[next_ch++] = seg[i].str[seg[i].len-1];
                hash[ seg[i].str[seg[i].len-1]-'a' ] = 1;
            }
        }

        work ( n );
    }
}