codeforces 510 C Fox And Names【拓扑排序】

题意:给出n串名字,表示字典序从小到大,求符合这样的字符串排列的字典序

先挨个地遍历字符串,遇到不相同的时候,加边,记录相应的入度

然后就是bfs的过程,如果某一点没有被访问过,且入度为0,则把它加入队列中,并将它指向的节点的入度减去1

另外如果len[i]<len[i-1],说明第i个字符串是i-1个字符串的前缀,但是它还排在后面,这样肯定不存在符合的字典序,直接输出“Impossible”

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int e[maxn],first[maxn],next[maxn],ans[maxn],len[maxn],vis[maxn],in[maxn];
char s[][];
int ecnt; void addedges(int u,int v){
e[ecnt]=v;
next[ecnt]=first[u];
first[u]=ecnt;
in[v]++;
ecnt++;
} int main(){ // freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
cin>>n; memset(first,-,sizeof(first));
for(int i=;i<=n;i++){
cin>>s[i];
len[i]=strlen(s[i]);
} int j;
ecnt=;
for(int i=;i<=n;i++){
for(j=;j<min(len[i],len[i-]);j++){
if(s[i-][j]!=s[i][j]){
addedges(s[i-][j]-'a',s[i][j]-'a');
break;
}
}
if(len[i]<len[i-]&&j==len[i]){
printf("Impossible\n");
return ;
}
} memset(vis,,sizeof(vis)); for(int i=;i<=;i++){
int jj=;
int j;
for( j=;j<;j++){
if(!vis[j]&&in[j]==){
vis[j]=;
ans[i]=j;
for(int k=first[j];k!=-;k=next[k]){
in[e[k]]--;
}
jj=j;
break;
}
}
if(jj==){//jj的值没有发生改变,说明这 一点找不到符合的拓扑序
printf("Impossible\n");
return ;
}
} for(int i=;i<=;i++)
printf("%c",ans[i]+'a');
printf("\n");
return ;
}
上一篇:codeforces Unusual Product


下一篇:下了个蓝屏代码查看工具,就中病毒了。。。什么鬼病毒,竟然还是用的VBS