joj 1857 Catenyms

1857: Catenyms

Result
TIME Limit
MEMORY Limit
Run Times
AC Times
JUDGE
3s
8192K
84
십칠
Standard
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. 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. 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

Output for Sample Input

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

 
This problem is used for contest: 171  
 
 
//어이가 없네 #include#include#includeusingnamespacestd;struct Edge { int u,v,next; char str[31]; } edge[1010]; bool cmp(Edge a,Edge b) { if(strcmp(a.str,b.str)>=0) return 1; else return 0; } int ttt; int od[31],id[31]; bool buse[31]; int p[31]; int head[31]; bool vis[2010]; int list[1010]; int n; int num; void ufset() { for(int i=0; i<26; i++) p[i]=i; } int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } void Union(int r1,int r2) { int t1=find(r1); int t2=find(r2); p[t1]=t2; } bool bsconnect() { int u,v; ufset(); int i; for(i=0; i0;i--) printf("%s.",edge[list[i]].str); printf("%s/n",edge[list[0]].str); } int main() { int T; int u,v; scanf("%d",&T); while(T--) { memset(od,0,sizeof(od)); memset(id,0,sizeof(id)); memset(buse,0,sizeof(buse)); memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i=0; i=2||id[j]-od[j]>=2) { euler=false; break; } if(od[j]==0&&id[j]==0) { euler=false; break; } if(od[j]-id[j]==1) { one++; tt=j; if(one>1) { euler=false; break; } } if(id[j]-od[j]==1) { none++; if(none>1) { euler=false; break; } } } if(one!=none) euler=false; if(!bsconnect()) euler=false; if(euler) { sort(edge,edge+n,cmp); for(int i=0; i