fork(21) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. int e[27][27];
  6. string s[101];
  7. bool visited[27];
  8.  
  9. int getID(char c)
  10. {
  11. if(c == ' ') return 0;
  12. return c - 'a' + 1;
  13. }
  14.  
  15. int MAIN()
  16. {
  17. memset(e, 0, sizeof(e));
  18. for(int i = 1; i <= 26; i++)
  19. e[0][i] = true;
  20. cin >> n;
  21. for(int i = 1; i <= n; i++)
  22. {
  23. cin >> s[i];
  24. s[i] += " ";
  25. }
  26. for(int i = 1; i < n; i++)
  27. {
  28. int pos = 0;
  29. while(s[i][pos] == s[i+1][pos]) pos ++;
  30. e[getID(s[i][pos])][getID(s[i+1][pos])] = true;
  31. }
  32. for(int k = 0; k <= 26; k++)
  33. for(int i = 0; i <= 26; i++)
  34. for(int j = 0; j <= 26; j++)
  35. e[i][j] |= e[i][k] & e[k][j];
  36. bool haveCycle = false;
  37. for(int i = 0; i <= 26; i++)
  38. haveCycle |= e[i][i];
  39. if(haveCycle)
  40. cout << "Impossible" << endl;
  41. else
  42. {
  43. memset(visited, 0, sizeof(visited));
  44. for(int i = 0; i <= 26; i++)
  45. {
  46. int now = 0;
  47. for(int j = 0; j <= 26; j++)
  48. {
  49. bool valid = (!visited[j]);
  50. for(int k = 0; k <= 26; k++)
  51. if(visited[k] == false && e[k][j])
  52. valid = false;
  53. if(valid)
  54. {
  55. now = j;
  56. break;
  57. }
  58. }
  59. if(i > 0)
  60. cout << char('a' + now - 1);
  61. visited[now] = true;
  62. }
  63. cout << endl;
  64. }
  65. return 0;
  66. }
  67.  
  68. int main()
  69. {
  70. #ifdef LOCAL_TEST
  71. freopen("in.txt", "r", stdin);
  72. freopen("out.txt", "w", stdout);
  73. #endif
  74. ios :: sync_with_stdio(false);
  75. cout << fixed << setprecision(16);
  76. return MAIN();
  77. }
  78.  
Success #stdin #stdout 0s 3284KB
stdin
Standard input is empty
stdout
abcdefghijklmnopqrstuvwxyz