看题目是字符串处理,但实际上是欧拉回路
#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 );
    }

}