POJ 2337 有向图的欧拉路径 - c++编程基础

Catenyms

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 8857		Accepted: 2336

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
***

单词接龙，形成欧拉路径。

计算方法：

（1) 在输入词典的同时构造有向图G，计算每一个节点所在的入度和并查集所在的根，

（2）将边按照字典序排列。

（3）按照递增顺序搜索每一个节点，若相邻两个节点属于不同的并查集，则说明图无法按照字典序形成若连通图，有向欧拉路径不存在。否则进行4

（4）按照递增顺序搜索每一个节点，若存在入度出度相差大于1的节点，则有向图欧拉路径不存在，否则，若所有的节点出入度相同，则选择序号最下的节点

作为欧拉回路的起点，若存在一个出度比入度大一的顶点，则该节点作为有向欧拉路径的起点，

（5）从S出发dfs计算有向图欧拉路径

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/25 19:03:35
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; const int maxn=1100; struct node{ int u,v; string name; }road[maxn]; int n,S,stop,t; bool cmp(node a,node b){ return a.name
                
                 1)return 0; sum++; if(out[i]>in[i])S=i; } } if(sum==0){ for(int i=1;i<26;i++) if(app[i]){ S=i; break; } } return 1; } void dfs(int now){ for(int i=1;i<=n;i++) if(!use[i]&&road[i].u==now){ use[i]=1; dfs(road[i].v); s[++stop]=i; } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int T; cin>>T; while(T--){ cin>>n; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(fa,0,sizeof(fa)); memset(app,0,sizeof(app)); for(int i=1;i<=n;i++){ cin>>road[i].name; road[i].u=road[i].name[0]-'a'+1; road[i].v=road[i].name[road[i].name.length()-1]-'a'+1; app[road[i].u]=1; app[road[i].v]=1; int u=find(road[i].u); int v=find(road[i].v); if(u!=v)fa[u]=v; out[road[i].u]++;in[road[i].v]++; } sort(road+1,road+n+1,cmp); if(!euler()){ puts("***"); continue; } stop=0; memset(use,0,sizeof(use)); dfs(S); for(int i=stop;i>=2;i--)cout<