2859034_ce.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int len[1001];
char d[1000][32], used[1001];
int i,j,k,m,n,c,tot,source,sink;
int ar[256], adj[256][256],out[1000];
int ad[256][256];

mark(char x){
   int i;
   for (i='a';i<='z';i++) {
      if (ad[x][i] > 0) {
         ad[x][i] = -1;
         mark(i);
      }
   }
}
   
reachable(char x) {
   int i,j;
   memcpy(ad,adj,sizeof(adj));
   mark(x);
   for (i='a';i<='z';i++) for (j='a';j<='z';j++)
      if (ad[i][j] > 0) return 0;
   return 1;
}

main(){
   scanf("%d",&c);
   while (c--) {
      scanf("%d",&n;
      memset(ar,0,sizeof(ar));
      memset(adj,0,sizeof(adj));
      tot = n-1;
      for (i=0;i<n;i++) {
         scanf(" %s",d[i]);len[i] = strlen(d[i])-1;
         ar[d[i][0]]--;
         ar[d[i][strlen(d[i])-1]]++;
         adj[d[i][0]][d[i][strlen(d[i])-1]]++;
      }
      qsort(d,n,32,strcmp);
      for (source = 'a'; source <= 'z' && ar[source]>=0; source++);
      if (source > 'z') source = d[0][0];
      memset(used,0,sizeof(used));
      for (j=0;j<n;j++) {
         for (i=0;i<n ;i++) {
            if (used[i]) continue;
            if (d[i][0] != source) continue;
            adj[d[i][0]][d[i][len[i]]]--;
            if (reachable(d[i][len[i]])) break;
            adj[d[i][0]][d[i][len[i]]]++;
         }
         if (i == n) break;
         out[j] = i;
         source = d[i][strlen(d[i])-1];
         used[i] = 1;
      }
      if (j < n) {
         printf("***\n");
      } else {
         for (i=0;i+1<n;i++) printf("%s.",d[out[i]]);
         printf("%s\n",d[out[n-1]]);
      }
   }
}