CF510C Fox And Names——拓扑排序练习

省委代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define maxn 100
#define maxm 10000 using namespace std; struct edge{
int next,to;
}e[maxm]; int point[maxn],cnt;
int l,r,q[maxn],in[maxn];
char s[110][110]; void addedge(int x,int y)
{
e[++cnt].next=point[x];
e[cnt].to=y;
point[x]=cnt;
} void toposort()
{
l=r=0;
for(int i=0;i<26;i++)
if(in[i]==0)
q[++r]=i;
while(l<r)
{
int x=q[++l];
for(int i=point[x];i;i=e[i].next)
{
int y=e[i].to;
in[y]--;
if(in[y]==0)
q[++r]=y;
}
}
} int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]);
for(int i=1;i<n;i++)
{
int len1=strlen(s[i]);
int len2=strlen(s[i+1]);
bool flag=0;
for(int j=0;j<min(len1,len2);j++)
if(s[i][j]==s[i+1][j])
continue;
else
{
flag=1;
in[s[i+1][j]-'a']++;
addedge(s[i][j]-'a',s[i+1][j]-'a');
break;
}
if(flag==0 && len2<len1)
{
printf("Impossible");
return 0;
}
}
toposort();
if(l<26)
printf("Impossible");
else
for(int i=1;i<=26;i++)
printf("%c",q[i]+'a');
return 0;
}
上一篇:[CF #290-C] Fox And Names (拓扑排序)


下一篇:java内存模型及内存与cpu之间的关系