➤ 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!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.