PKU 2337 오 라 회 로 판단 및 출력

http://acm.pku.edu.cn/JudgeOnline/problem?id=2337
 
Catenyms
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 4137
 
Accepted: 975
Description
A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,
aloha.aloha.arachnid.dog.gopher.rat.tiger
Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.
Input
The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.
Output
For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.
Sample Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger
***

Source
Waterloo local 2003.01.25
 
 
오로라 경 로 는 모든 단 어 를 한 변 으로 보고 이니셜 은 두 개의 노드 로 본다.즉,최대 26 개의 노드,그 다음 에 가장 소박 한 오로라 경로 알고리즘 이다.먼저 오로라 경로 의 존재 여 부 를 판단 한다.그러나 이 문 제 는 사전 순서 가 가장 작은 경 로 를 출력 하 는 것 이 요구 된다.이것 은 매우 간단 하 다.먼저 입력 한 단 어 를 어 릴 때 부터 줄 을 서서 그림 을 만 들 면 된다.
 
#include
using namespace std;
int degree_in[26],degree_out[26],edge_num,edge_order[1005];
bool used[1005];
struct Edge
{
       int start,end;
       char word[25];
}edges[1005];
int CMP(const void* a,const void* b)
{
       Edge *c=(Edge*)a,*d=(Edge*)b;
       if(c->start!=d->start) return c->start-d->start;
       else return strcmp(c->word,d->word);
}
inline int ABS(int a)
{
       if(a>0) return a;
       else return -a;
}
int check()//시작 점 되 돌리 기
{
       int cnt1=0,cnt2=0,source;
       for(int i=0;i<26;i++)
       {
              if(ABS(degree_in[i]-degree_out[i])==2)
                     return -1;
              else if(degree_in[i]-degree_out[i]==1)
                     cnt1++;
              else if(degree_in[i]-degree_out[i]==-1)
              {
                     cnt2++;
                     source=i;
              }
       }
       if(cnt1>1||cnt2>1)
              return -1;
       else if(cnt1==0)
       {
              for(int i=0;i<26;i++)
                     if(degree_out[i])
                            return i;
       }
       else return source;
}
bool solve_dfs(int source,int cnt)
{
       if(cnt==edge_num) return true;
       for(int i=0;i       {
              if(edges[i].start                     continue;
              else if(edges[i].start>source)
                     return false;
              used[i]=true;
              edge_order[cnt]=i;
              if(solve_dfs(edges[i].end,cnt+1)) return true;
              used[i]=false;
       }
       return false;
}
int main()
{
       int t;
       scanf("%d",&t);
       while(t--)
       {
              memset(degree_out,0,sizeof(degree_out));
              memset(degree_in,0,sizeof(degree_in));
              scanf("%d",&edge_num);
              for(int i=0;i              {
                     scanf("%s",edges[i].word);
                     edges[i].start=edges[i].word[0]-'a';
                     edges[i].end=edges[i].word[strlen(edges[i].word)-1]-'a';
                     degree_out[edges[i].start]++;
                     degree_in[edges[i].end]++;
              }
              int source=check();
              if(source==-1)
              {
                     printf("***/n");
                     continue;
              }
              qsort(edges,edge_num,sizeof(edges[0]),CMP);
              memset(used,0,sizeof(used));
              if(!solve_dfs(source,0))
              {
                     printf("***/n");
                     continue;
              }
              printf("%s",edges[edge_order[0]].word);
              for(int i=1;i              {
                     printf(".%s",edges[edge_order[i]].word);
              }
              printf("/n");
       }
}