fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool multicases_=false;
  5. #define int long long
  6.  
  7. string ans;
  8.  
  9. map<char,vector<char>>adj;
  10. bool cycle=false;
  11. map<char,int>vis;
  12.  
  13. void dfs(char node){
  14.  
  15. 	vis[node]=1;
  16.  
  17. 	//dbg:
  18. 	// cerr<<node<<'\n';
  19.  
  20. 	for(auto&child:adj[node]){
  21. 		if(vis[child]==0){
  22. 			dfs(child);
  23. 		} else if(vis[child]==1){
  24. 			cycle=true;
  25. 			return;
  26. 		}
  27. 	}
  28.  
  29.  
  30. 	vis[node]=2;
  31. 	ans+=node;
  32. }
  33.  
  34. void solve(int tc){
  35. 	// //dbg:
  36. 	 // cerr<<"at the test case no."<<tc<<" : \n";
  37.  
  38.  
  39. 	int n;cin>>n;//input
  40. 	string s;
  41. 	for(int i= 0 ;i <n ; i++){
  42. 		cin>>s;
  43.  
  44. 		string tmp="";
  45. 		tmp+=s[0];
  46. 		for(int i = 1; i < (int)s.size(); i++){
  47. 			if(s[i]!=s[i-1]){
  48. 				tmp+=s[i];
  49. 			}
  50. 		}
  51.  
  52. 		s=tmp;
  53.  
  54. 		for(int i = 1 ;i < (int)s.size(); i++){
  55. 			adj[s[i-1]].push_back(s[i]);
  56.  
  57. 			//dbg <<<<<<<<<<<<<<<<<<<<<<<
  58. 			// cerr<<s[i-1]<<" > "<<s[i]<<" , ";
  59.  
  60. 		}
  61.  
  62. 	}
  63.  
  64. 	for(auto&[node,children]:adj){
  65. 		if(!vis[node]){
  66. 			dfs(node);
  67. 		}
  68. 		if(cycle) break;
  69. 	}
  70.  
  71. 	if(!cycle){
  72.  
  73. 		reverse(ans.begin(),ans.end());///////////////fix
  74.  
  75. 		char c;
  76. 		for(int i = 0 ;i <26 ;i++){
  77. 			c='a'+i;
  78. 			if(!vis[c]) ans+=c;
  79. 		}
  80. 	}
  81.  
  82. 	if(cycle) cout<<"NAO";
  83. 	else cout<<"SIM\n"<<ans;
  84.  
  85.  
  86. 	// //dbg:
  87. 	// for(auto&[node,children]:adj){
  88. 		// cerr<<node<<endl;
  89. 		// for(auto&child:children) cerr<<child<<' ';
  90. 	// }
  91.  
  92.  
  93. }
  94.  
  95. signed main(){
  96. 	ios::sync_with_stdio(0);cin.tie(0);
  97.  
  98. 	//pre computations:
  99.  
  100.  
  101. 	int tc=1;
  102. 	if(multicases_)cin>>tc;
  103. 	int total_tcs=tc;
  104. 	while(tc--){
  105. 		solve(total_tcs-tc);
  106. 	}
  107. 	return 0;
  108. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3
abc
def
ghi
stdout
copy 
SIM
ghidefabcjklmnopqrstuvwxyz
https://ideone.com/NfLhRZ
language:
C++14 (gcc 8.3)
created:
1 hour 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!