fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <list>
  6. #include <string.h>
  7. using namespace std;
  8.  
  9. vector<vector<int> > adj;
  10. void makeGraph(const vector<string>& words) {
  11.     adj = vector<vector<int> >(26, vector<int>(26, 0));
  12. 	for (int j=1; j<words.size(); ++j) {
  13. 		int i = j-1, len = min(words[i].size(), words[j].size());
  14. 		for (int k=0; k<len; ++k) {
  15. 			if (words[i][k] != words[j][k]) {
  16. 				int a = words[i][k] - 'a';
  17. 				int b = words[j][k] - 'a';
  18.  
  19. 				printf("%c --> %c\n",a+97,b+97);
  20. 				adj[a][b] = 1;
  21. 				break;
  22. 			}
  23. 		}
  24. 	}
  25. }
  26.  
  27. vector<int> seen, order;
  28. void dfs(int here) {
  29. 	seen[here] = 1;
  30. 	for (int there=0; there<adj.size(); ++there)
  31. 		if (adj[here][there] && !seen[there])
  32. 			dfs(there);
  33.  
  34. 	order.push_back(here);
  35. }
  36.  
  37. vector<int> topologicalSort() {
  38. 	int n = adj.size();
  39. 	seen = vector<int>(n, 0);
  40. 	order.clear();
  41.  
  42. 	for (int i=0; i<n; ++i)
  43. 		if (!seen[i])
  44. 			dfs(i);
  45.  
  46. 	reverse(order.begin(), order.end());
  47.  
  48. 	for (int i=0; i<n; ++i)
  49. 		for (int j=i+1; j<n; ++j)
  50. 			if (adj[order[j]][order[i]])
  51. 				return vector<int>();
  52.  
  53. 	return order;
  54. }
  55.  
  56. int main()
  57. {
  58. 	int c;
  59. 	cin >> c;
  60. 	while (c--) {
  61. 		int n;
  62. 		vector<string> words;
  63.  
  64. 		cin >> n;
  65. 		for (int i=0; i<n; i++) {
  66. 			string t;
  67. 			cin >> t;
  68. 			words.push_back(t);
  69. 		}
  70.  
  71. 		makeGraph(words);
  72. 		vector<int> ret = topologicalSort();
  73.  
  74. 		for (int i=0; i<ret.size(); i++) {
  75. 			printf("%c",ret[i]+97);
  76. 			//printf("%d ",ret[i]);
  77. 		}
  78.  
  79. 		cout << endl;
  80. 	}
  81. }
  82.  
Success #stdin #stdout 0s 2996KB
comments (?)
stdin
copy 
3
3
ba
aa
ab
5
gg
kia
lotte
lg
hanhwa
6
dictionary
english
is
ordered
ordinary
this
stdout
copy 
b --> a
a --> b

g --> k
k --> l
o --> g
l --> h
zyxwvutsrqponmjigklhfedcba
d --> e
e --> i
i --> o
e --> i
o --> t
zyxwvusrqpnmlkjhgfdeiotcba
https://ideone.com/6KObzC
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

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!