fork(28) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
abcdefghijklmnopqrstuvwxyz
https://ideone.com/KVobNb
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!