Share Pastebin
Guest
Public paste!

Untitled

By: a guest | Mar 19th, 2010 | Syntax: None | Size: 1.72 KB | Hits: 70 | Expires: Never
Copy text to clipboard
  1. include <cstdio>
  2. include <string>
  3. include <cstring>
  4. include <algorithm>
  5. include <vector>
  6. using namespace std;
  7.  
  8. define EXT 5
  9.  
  10. int N;
  11. int V1, V2;
  12. int lastv;
  13. int countv;
  14. int indeg[26];
  15. int outdeg[26];
  16. bool used[26];
  17. bool mat[26][26];
  18.  
  19. inline int get_number(){
  20. register char c;
  21. register int n = 0;
  22. while((c = getc_unlocked(stdin) ) != '\n'){
  23. n *= 10;
  24. n += ( c - '0' );
  25. }
  26. return n;
  27. }
  28.  
  29. inline void get_vertexes(){
  30. register char c;
  31. register char t;
  32. V1 = getc_unlocked(stdin)-'a';
  33. while((c = getc_unlocked(stdin)) != '\n'){
  34. t = c;
  35. }
  36. V2 = t-'a';
  37. }
  38.  
  39. inline void go(int &v){
  40. countv--;
  41. used[v] = false;
  42. for(int i = 0; i < 26; i++){
  43. if(used[i] && mat[v][i]){
  44. go(i);
  45. }
  46. }
  47. }
  48.  
  49. inline bool solve(){
  50. N = get_number();
  51. memset(mat,false,sizeof(mat));
  52. memset(indeg,0,sizeof(indeg));
  53. memset(outdeg,0,sizeof(outdeg));
  54. memset(used,false,sizeof(used));
  55. while(N--){
  56. get_vertexes();
  57. outdeg[V1]++;
  58. indeg[V2]++;
  59. used[V1] = true;
  60. used[V2] = true;
  61. lastv = V1;
  62. mat[V1][V2] = true;
  63. }
  64. int count = 0;
  65. int p[2];
  66. countv = 0;
  67. for(int i = 0; i < 26; i++){
  68. if(used[i]){
  69. countv++;
  70. if(indeg[i]!=outdeg[i]){
  71. if(count>=2) return false;
  72. p[count] = i;
  73. count++;
  74. }
  75. }
  76. }
  77. if(count==1) return false;
  78. if(count==2){
  79. int v1 = p[0];
  80. int v2 = p[1];
  81. if(indeg[v1]>outdeg[v1]){
  82. if(indeg[v1]-outdeg[v1]!=1) return false;
  83. if(outdeg[v2]-indeg[v2]!=1) return false;
  84. mat[v1][v2] = true;
  85. }else{
  86. if(indeg[v2]-outdeg[v2]!=1) return false;
  87. if(outdeg[v1]-indeg[v1]!=1) return false;
  88. mat[v2][v1] = true;
  89. }
  90. }
  91. go(lastv);
  92. return countv == 0;
  93. }
  94.  
  95. int main(){
  96. int T = get_number();
  97. while(T--){
  98. if(solve()){
  99. fputs_unlocked("Ordering is possible.\n", stdout);
  100. }else{
  101. fputs_unlocked("The door cannot be opened.\n", stdout);
  102. }
  103. }
  104. }