C   31
visit
Guest on 11th February 2023 01:23:17 AM


  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #define max 10000
  5. int c;
  6. int map[30][30];
  7. int dot[30], in[30], out[30], total, ok, check[30], ap[30];
  8. void visit(int d){
  9.         int i;
  10.         for(i=0; i<total; i++){
  11.                 if(map[ap[d]][ap[i]] == 1 && check[i] == 0){
  12.                         check[i] = 1;
  13.                         c++;
  14.                         visit(i);
  15.                 }      
  16.         }
  17. }
  18. int main(){
  19.         char input[1002];
  20.         int N, n, len, i, j, k, odd, t;
  21.         scanf("%d", &N);
  22.         while(N--){
  23.                 scanf("%d", &n);
  24.                 for(i=0; i<26; i++){
  25.                         for(j=i; j<26; j++){
  26.                                 map[i][j] = map[j][i] = max;
  27.                         }      
  28.                 }
  29.                 memset(out, 0, sizeof(out));
  30.                 memset(in, 0, sizeof(in));
  31.                 memset(check, 0, sizeof(check));
  32.                 total = 0;
  33.                 while(n--){
  34.                         scanf("%s", input);
  35.                         len = strlen(input);
  36.                         map[input[0]-='a'][input[len-1]-='a'] = 1;
  37.                         if(out[input[0]] == 0 && in[input[0]] == 0){
  38.                                 ap[total] = input[0];
  39.                                 total++;
  40.                         }
  41.                         out[input[0]]++;
  42.                         if(out[input[len-1]] == 0 && in[input[len-1]] == 0){
  43.                                 ap[total] = input[len-1];
  44.                                 total++;
  45.                         }
  46.                         in[input[len-1]]++;
  47.                 }
  48.                 odd = 0;
  49.                 for(i=0; i<26; i++){
  50.                         if(out[i] - in[i] == 1){
  51.                                 odd += (1<<1);
  52.                                 for(j=0; j<total; j++){
  53.                                         if(ap[j] == i){
  54.                                                 t = j;
  55.                                                 break; 
  56.                                         }      
  57.                                 }
  58.                         }else if(in[i] - out[i] == 1){
  59.                                 odd += (1<<2);
  60.                         }else if(out[i] - in[i]){
  61.                                 odd += (1<<3);
  62.                                 break; 
  63.                         }
  64.                         if(odd >= 6){
  65.                                 break; 
  66.                         }
  67.                 }
  68.                 if((odd & 1<<3) != 0){
  69.                         puts("The door cannot be opened.");
  70.                 }else if(odd == 6 || odd == 0){
  71.                         c = 1;
  72.                         if(odd == 6){
  73.                                 check[t] = 1;
  74.                                 visit(t);
  75.                         }else{
  76.                                 check[0] = 1;
  77.                                 visit(0);      
  78.                         }
  79.                         if(c == total) puts("Ordering is possible.");
  80.                         else puts("The door cannot be opened.");
  81.                 }              
  82.         }
  83.  
  84.  
  85.     getchar();
  86.     return 0;
  87. }
Raw Paste

Login or Register to edit or fork this paste. It's free.