➤ Problem Link : 510C. Fox And Names
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; bool visited[26]; bool recStack[26]; bool dfs(int v,vector<int> adj[],stack<char> & s) { recStack[v]=1; for(int i=0;i<adj[v].size();i++) { if(recStack[adj[v][i]]) return 1; if(!visited[adj[v][i]]) { visited[adj[v][i]]=1; if(dfs(adj[v][i],adj,s)) return 1; } } s.push(v+97); recStack[v]=0; return 0; } int main() { int n; string st; cin>>n; vector<string> v; for(int i=0;i<n;i++) { cin>>st; v.push_back(st); } vector<int> adj[26]; for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(v[i].length()>v[j].length() && v[i].substr(0,v[j].length())==v[j]) { cout<<"Impossible"; exit(0); } for(int k=0;k<min(v[i].length(),v[j].length());k++) { if(v[i][k]==v[j][k]) continue; else { adj[v[i][k]-'a'].push_back(v[j][k]-'a'); break; } } } } memset(visited,0,sizeof(visited)); memset(recStack,0,sizeof(recStack)); stack<char> s; bool flag=0; for(int i=0;i<26;i++) { if(!visited[i]) { visited[i]=1; if(dfs(i,adj,s)) { flag=1; break; } } } if(flag) cout<<"Impossible"; else while(!s.empty()) { cout<<s.top(); s.pop(); } }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!