fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <stack>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int G[26][26]; //graph
  8. vector<string> save[26][26];
  9. int deg[26];
  10. vector<int> res;
  11. stack<int> st;
  12. int main() {
  13. 	// your code goes here
  14. 	int N;
  15. 	cin >> N;
  16. 	for (int i=0; i < N; i++){
  17. 		string t;
  18. 		cin >> t;
  19. 		int a = t[0]-'a';
  20. 		int b = t[t.length() - 1] - 'a'; 
  21. 		G[a][b]++;
  22. 		save[a][b].push_back(t);
  23. 		deg[a]++;
  24. 		deg[b]--;
  25. 	}
  26. 	int tStart = -1;
  27. 	int tFinish = -1;
  28. 	for (int i=0; i < 26; i++)
  29. 		if (!deg[i]) ;
  30. 		else if (deg[i] == 1 && tStart == -1)
  31. 			tStart = i;
  32. 		else if (deg[i] == -1 && tFinish == -1)
  33. 			tFinish = i;
  34. 		else {
  35. 			cout << "NO"<<endl;
  36. 			return 0;
  37. 		}
  38. 	if (tStart == -1)
  39. 		tStart = 0;
  40. 	st.push(tStart);
  41. 	while (!st.empty()){
  42. 		int v = st.top();
  43. 		int i;
  44. 		for (i=0; i<26; ++i)
  45. 			if (G[v][i])
  46. 				break;
  47. 		if (i == 26){
  48. 			res.push_back (v);
  49. 			st.pop();
  50. 		}
  51. 		else {
  52. 			G[v][i]--;
  53. 			st.push (i);
  54. 		}
  55. 	}
  56. 	if (res.size() - 1 != N){
  57. 		cout << "NO"<<endl;
  58. 		return 0;	
  59. 	}
  60. 	for (int i=res.size()-1; i ; i--){
  61. 		cout << save[ res[i] ][res[i-1]].back()<<endl;
  62. 		 save[ res[i] ][res[i-1]].pop_back();
  63. 	}
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
4
b
ab
bc
bb
stdout
copy 
ab
bb
b
bc
https://ideone.com/zvqa9m
language:
C++14 (gcc 8.3)
created:
4 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!