典型的建模
对于每个字符串 视为从首字母向尾字母连一条边
跑一下欧拉路即可
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<vector> 7 #include<iostream> 8 #include<iomanip> 9 #define itn int 10 #define ms(a,b) memset(a,b,sizeof a) 11 #define rep(i,a,n) for(int i = a;i <= n;i++) 12 #define per(i,n,a) for(int i = n;i >= a;i--) 13 #define inf 2147483647 14 using namespace std; 15 typedef long long ll; 16 ll read() { 17 ll as = 0,fu = 1; 18 char c = getchar(); 19 while(c < '0' || c > '9') { 20 if(c == '-') fu = -1; 21 c = getchar(); 22 } 23 while(c >= '0' && c <= '9') { 24 as = as * 10 + c - '0'; 25 c = getchar(); 26 } 27 return as * fu; 28 } 29 //head 30 const int N = 10006; 31 int n; 32 struct line { 33 int x,y,l; 34 char s[30]; 35 bool operator < (const line &o) const { 36 rep(i,0,min(l-1,o.l-1)) { 37 if(s[i] < o.s[i]) return 1; 38 if(s[i] > o.s[i]) return 0; 39 } 40 if(l < o.l) return 1; 41 return 0; 42 } 43 void read() { 44 scanf("%s",s); 45 l = strlen(s); 46 x = s[0] - 'a' + 1,y = s[l-1] - 'a' + 1; 47 } 48 }a[N]; 49 int rdu[30],cdu[30]; 50 51 bool vis[N]; 52 int stk[N],top; 53 void dfs(int x) { 54 rep(i,1,n) if(a[i].x == x && !vis[i]) { 55 vis[i] = 1,dfs(a[i].y),stk[++top] = i; 56 } 57 } 58 int str; 59 int main() { 60 n = read(); 61 rep(i,1,n) a[i].read(); 62 sort(a+1,a+n+1); 63 rep(i,1,n) rdu[a[i].y]++,cdu[a[i].x]++; 64 65 rep(i,1,26) if(cdu[i] == rdu[i] + 1) str = i; 66 if(!str) rep(i,1,26) if(cdu[i]) {str = i;break;} 67 68 dfs(str); 69 70 if(top < n) puts("***"),exit(0); 71 while(top) { 72 printf("%s",a[stk[top]].s); 73 if(--top) putchar('.'); 74 } 75 return 0; 76 }