poj2337欧拉回路要求输出路径

Catenyms

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 8368		Accepted: 2202

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

用DFS实现的

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <algorithm>
  4 #include <string.h>
  5 #include <math.h>
  6 #include <vector>
  7 #include <stack>
  8 #include <map>
  9 using namespace std;
 10 #define ll long long int
 11 #define INF 5100000
 12 string a[1500];
 13 int v[2000];
 14 vector<pair<int,int> >aa[30];
 15 vector<int>ab;
 16 int p[30];
 17 int d1[30];
 18 int d2[30];
 19 int find(int x)
 20 {
 21     while(x!=p[x])
 22         x=p[x];
 23     return x;
 24 }
 25 void fun(int x,int eid)
 26 {
 27     for(int i=0; i<aa[x].size(); i++)
 28         if(!v[aa[x][i].second])
 29         {
 30             v[aa[x][i].second]=true;
 31             fun(aa[x][i].first,aa[x][i].second);
 32         }
 33     if(eid>0)ab.push_back(eid);
 34 }
 35 int main()
 36 {
 37     int tt;
 38     int i,j;
 39     cin>>tt;
 40     for(i=0; i<tt; i++)
 41     {
 42         int n;
 43         cin>>n;
 44         memset(d1,0,sizeof(d1));
 45         memset(d2,0,sizeof(d2));
 46         for(j=1; j<30; j++)
 47             p[j]=j,aa[j].clear();
 48         for(j=1; j<=n; j++)
 49         {
 50             cin>>a[j];
 51         }
 52         sort(a+1,a+n+1);
 53         for(j=1; j<=n; j++)
 54         {
 55             int x=a[j][0]-'a'+1;
 56             int y=a[j][a[j].length()-1]-'a'+1;
 57             d1[x]++;
 58             d2[y]++;
 59             aa[x].push_back(make_pair(y,j));
 60             int fx=find(x);
 61             int fy=find(y);
 62             if(fy!=fx)
 63                 p[fy]=fx;
 64         }
 65         int sum=0;
 66         int start=a[1][0]-'a'+1;
 67         for(j=1; j<30; j++)
 68         {
 69             if(d1[j]==0&&d2[j]==0)continue;
 70             if(p[j]==j)sum++;
 71         }
 72         if(sum>1)
 73             cout<<"***"<<endl;
 74         else
 75         {
 76             int dd1=0,dd2=0;
 77             for(j=1; j<30; j++)
 78             {
 79                 if(d1[j]!=d2[j])
 80                 {
 81                     if(d1[j]-d2[j]==1)
 82                         dd1++,start=j;
 83                     else if(d2[j]-d1[j]==1)
 84                         dd2++;
 85                     else
 86                     {
 87                         dd2=199;
 88                         break;
 89                     }
 90                 }
 91             }
 92             if(dd2<=1&&dd1<=1)
 93             {
 94                 memset(v,0,sizeof(v));
 95                 ab.clear();
 96                 fun(start,0);
 97                 for( j=ab.size()-1; j>=0; j--)
 98                 {
 99                     cout<<a[ab[j]];
100                     if(j!=0)cout<<".";
101                     else cout<<"
";
102                 }
103 
104             }
105             else cout<<"***"<<endl;
106         }
107     }
108 }

View Code