繁华模拟赛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 ;

}