poj2337 Catenyms

#include"stdio.h"
#include"math.h"
#include"string.h"
#include"stdlib.h"

typedef struct node
{
        int from,to,vis;
        
}Node;
Node map[1001];
char str[1001][21],str1[1001][21];
int po[27];
int m,n,e;

int cmp(const void *a,const void *b)
{
        return strcmp((char *)a,(char *)b);
}

int find(int x)
{
        int i,j;
        i = x;
        while(x!=po[x])x = po[x];
        
        while(i!=x)
        {
                j     = po[i];
                po[i] = x;
                i     = j;
        }
        return x;
}

void eurlar(int u)
{
        int i;
        
        for(i=1;i<=e;i++)
        {
                if(!map[i].vis && map[i].from==u)
                {
                        map[i].vis = 1;
                        eurlar(map[i].to);
                        strcpy(str1[++n],str[i]);
                }
        }
}

int main()
{
        int text,i,j,k,len,a,b,a1,a2,in[27],out[27],us[27];
        
        scanf("%d",&text);
        while(text--)
        {
                scanf("%d",&e);
                if(e<3){printf("***");printf("\n");continue;}
                for(i=1;i<=26;i++)po[i] = i;
                for(i=1;i<=26;i++)in[i] = out[i] = us[i] = 0;
                for(i=1;i<=e;i++)
                {
                        scanf("%s",str[i]);
                }
                qsort(str+1,e,sizeof(str[0]),cmp);
                //for(i=1;i<=e;i++)printf("%d %s\n",i,str[i]);
                for(i=1;i<=e;i++)
                {
                        len = strlen(str[i]);
                        a = str[i][0]-'a'+1;
                        b = str[i][len-1]-'a'+1;//printf("a = %d b = %d \n",a,b);
                        a1= find(a);//并查集
                        a2= find(b);
                        po[a1] = a2;
                        map[i].from = a;
                        map[i].to   = b;
                        map[i].vis  = 0;
                        us[a]       = 1;
                        us[b]       = 1;                    
                        out[a]++;
                        in[b]++;
                }
                a = b = 0;
                for(i=1;i<=26;i++)//是不是在一棵树内
                {//printf("i = %d  po[] = %d us= %d\n",i,po[i],us[i]);
                        if(i==po[i] && us[i])b++;
                }//printf("b = %d\n",b);
                if(b>1)
                {
                        printf("***");
                        printf("\n");
                        continue;
                }
                a = b = 0;
                for(i=1;i<=26;i++)//入度和出度是否相等，且至多有一对差1
                {
                        if(in[i]==out[i])continue;//{printf("in=%d,out=%d\n",in[i],out[i]);continue;}
                        else if(in[i]-1==out[i])a++;
                        else if(in[i]+1==out[i])b++;
                        else break;
                }//printf("i =%d,a=%d,b=%d\n",i,a,b);
                if(i<=26 || a!=b || a>1 || b>1)
                {
                        printf("***\n");
                        continue;
                }
                n = 0;
                a1 = 1;
                
                if(a==1)//这是很严重的问题，当是欧拉路对时候，要找到原点，不然结果只是wa
                {
                        for(i=1;i<=e;i++)
                        {
                                if(out[map[i].from]-in[map[i].from]==1)//找到起点
                                {
                                        a1 = i;
                                        break;
                                }
                        }
                }
                eurlar(map[a1].from);
                for(i=n;i>=1;i--)
                {
                        printf("%s",str1[i]);
                        if(i>1)printf(".");
                }
                printf("\n");
        }
        return 0;
}