本文主要是介绍codeforces 290div2 C.Fox And Names,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
拓扑排序。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=100005;
char s[105][105];
int n;
int g[26][26];
int d[26];
int vis[26];
int t;
bool toposort();
bool solve(int a,int b);
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)scanf("%s",s[i]);memset(g,0,sizeof(g));for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(!solve(i,j)){printf("Impossible\n");return 0;}}}if(toposort()){for(int i=0;i<26;i++)printf("%c",(char)d[i]+'a');}elseprintf("Impossible\n");return 0;
}
bool solve(int a,int b)
{int len1=strlen(s[a]);int len2=strlen(s[b]);int len=min(len1,len2);for(int i=0;i<len;i++){if(s[a][i]!=s[b][i]){g[s[a][i]-'a'][s[b][i]-'a']=1;return true;}}if(len1<=len2)//trickreturn true;return false;
}
bool dfs(int u)
{vis[u]=-1;//正在访问中for(int i=0;i<26;i++){if(g[u][i]){if(vis[i]==1)continue;if(vis[i]==-1)//有环,失败退出return false;if(!dfs(i))return false;}}vis[u]=1;d[--t]=u;return true;
}
bool toposort()
{memset(vis,0,sizeof(vis));t=26;for(int i=0;i<26;i++){if(!vis[i]){if(!dfs(i))return false;}}return true;
}
这篇关于codeforces 290div2 C.Fox And Names的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!