繁华模拟赛day8 字典序

时间:2022-05-19 23:10:39

繁华模拟赛day8 字典序

繁华模拟赛day8 字典序

繁华模拟赛day8 字典序

/*
这个题要我们求一个字典序,字符串给出的顺序,会对字母的字典序前后相对顺序进行限定,如何用来表示这种限定,我们注意到这种一个之后接着一个,只有先输出他前面的才能输出他,很明显就是拓扑排序,最小方案只要优先队列随便搞一搞就行了
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = ;
struct edge{
int v;
int nxt;
}e[maxn*];
int n,l[maxn],ans[maxn],orz;
int head[maxn],cnt,du[maxn];
char sb[maxn][maxn];
priority_queue< int , vector<int> , greater<int> > q;
int read(){
char ch=getchar();
int x=,f=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
void ins(int u,int v){
cnt++;
e[cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void build(){
int j;
for(int i = ;i <= n;i++){
j = ;
while(j <= l[i-] && j <= l[i] && sb[i][j] == sb[i-][j]) j++;
if(j > l[i-] || j > l[i] || sb[i][j] == sb[i-][j]) continue;
ins(sb[i-][j]-'a',sb[i][j]-'a');
du[sb[i][j]-'a']++;
}
}
bool topo(){
int u,to;
for(int i = ;i < ;i++){
if(!du[i]) q.push(i);
}
while(!q.empty()){
ans[++orz] = q.top();
q.pop();
u = ans[orz];
for(int i = head[u];i;i=e[i].nxt){
to = e[i].v;
du[to]--;
if(!du[to]){
q.push(to);
}
}
}
return orz == ;
}
int main(){
freopen("lexicographical.in","r",stdin);
freopen("lexicographical.out","w",stdout);
n = read();
for(int i = ;i <= n;i++){
scanf("%s",sb[i]+);
l[i] = strlen(sb[i]+);
}
build();
if(!topo()) cout<<"Impossible";
else{
for(int i = ;i <= ;i++){
char tmp = ans[i] + 'a';
cout<<tmp;
}
}
return ;
}