510C. Fox And Names - Codeforces Solution C++

  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!!