洛谷P1127-词链

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <string>
  6 #include <stack>
  7 #include <algorithm>
  8 using namespace std;
  9 
 10 const int maxn = 1000+10;
 11 const int maxm = maxn*maxn;
 12 
 13 int n,tot,head[maxn];
 14 int len[maxn];
 15 bool vis[maxn];
 16 string str[maxn];
 17 
 18 struct Edge{
 19     int to,next;
 20     Edge(int to = 0,int next = 0) : to(to),next(next) {}
 21 }edge[maxm<<1];
 22 
 23 void AddEdge(int u,int v){
 24     edge[tot].to = v;
 25     edge[tot].next = head[u];
 26     head[u] = tot++;
 27 }
 28 
 29 int top,sta[maxn<<1];
 30 
 31 void output(){
 32     cout << str[sta[1]];
 33     for(int i = 2;i <= n;i++){
 34         printf(".");
 35         cout << str[sta[i]];
 36     }
 37     cout << endl;
 38     exit(0);
 39 }
 40 
 41 void dfs(int u){
 42     vis[u] = true;
 43     sta[++top] = u;
 44     for(int i = head[u];i != -1;i = edge[i].next){
 45         int v = edge[i].to;
 46         if(!vis[v]) dfs(v);
 47     }
 48     if(top == n) output();
 49     vis[u] = false;
 50     top--;
 51 }
 52 
 53 const int kind = 26;
 54 int con[maxn];
 55 
 56 int main()
 57 {
 58     //freopen("input.txt","r",stdin);
 59     cin >> n;
 60     for(int i = 1;i <= n;i++){
 61         cin >> str[i];
 62     }
 63     sort(str+1,str+1+n);
 64     top = 0;
 65     memset(head,-1,sizeof(head));
 66     memset(vis,false,sizeof(vis));
 67     memset(con,0,sizeof(con));
 68     for(int i = 1;i <= n;i++){
 69         len[i] = str[i].size();
 70     }
 71     for(int i = 1;i <= n;i++){
 72         for(int j = n;j >= 1;j--){
 73             if(i!=j && str[i][len[i]-1] == str[j][0]){
 74                 AddEdge(i,j);
 75             }
 76         }
 77     }
 78     for(int i = 1;i <= n;i++){
 79         con[str[i][0]-‘a‘]++;
 80         con[str[i][len[i]-1]-‘a‘]--;
 81     }
 82     int head = -1,cnt = 0,_cnt = 0;
 83     for(int i = 0;i < kind;i++){
 84         if(con[i] == 1){
 85             head = i;
 86             cnt++;
 87         }
 88         else if(con[i] == -1){
 89             _cnt++;
 90         }
 91      }
 92      if(cnt==0 && _cnt==0){
 93         for(int i = 1;i <= n;i++){
 94             dfs(i);
 95         }
 96      }
 97      else if(cnt==1 && _cnt==1){
 98         for(int i = 1;i <= n;i++){
 99             if(str[i][0]-‘a‘ == head) dfs(i);
100         }
101      }
102      printf("***\n");
103     return 0;
104 }